Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
You are given a string s. s[i] is either a lowercase English letter or '?'.
For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i - 1].
The value of t is the sum of cost(i) for all indices i.
For example, for the string t = "aab":
cost(0) = 0cost(1) = 1cost(2) = 0"aab" is 0 + 1 + 0 = 1.Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized.
Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.
Example 1:
Input: s = "???"
Output: "abc"
Explanation: In this example, we can replace the occurrences of '?' to make s equal to "abc".
For "abc", cost(0) = 0, cost(1) = 0, and cost(2) = 0.
The value of "abc" is 0.
Some other modifications of s that have a value of 0 are "cba", "abz", and, "hey".
Among all of them, we choose the lexicographically smallest.
Example 2:
Input: s = "a?a?"
Output: "abac"
Explanation: In this example, the occurrences of '?' can be replaced to make s equal to "abac".
For "abac", cost(0) = 0, cost(1) = 0, cost(2) = 1, and cost(3) = 0.
The value of "abac" is 1.
Constraints:
1 <= s.length <= 105s[i] is either a lowercase English letter or '?'.Problem summary: You are given a string s. s[i] is either a lowercase English letter or '?'. For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i - 1]. The value of t is the sum of cost(i) for all indices i. For example, for the string t = "aab": cost(0) = 0 cost(1) = 1 cost(2) = 0 Hence, the value of "aab" is 0 + 1 + 0 = 1. Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized. Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Greedy
"???"
"a?a?"
lexicographically-smallest-string-after-substring-operation)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
class Solution {
public String minimizeStringValue(String s) {
int[] cnt = new int[26];
int n = s.length();
int k = 0;
char[] cs = s.toCharArray();
for (char c : cs) {
if (c == '?') {
++k;
} else {
++cnt[c - 'a'];
}
}
PriorityQueue<int[]> pq
= new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
for (int i = 0; i < 26; ++i) {
pq.offer(new int[] {cnt[i], i});
}
int[] t = new int[k];
for (int j = 0; j < k; ++j) {
int[] p = pq.poll();
t[j] = p[1];
pq.offer(new int[] {p[0] + 1, p[1]});
}
Arrays.sort(t);
for (int i = 0, j = 0; i < n; ++i) {
if (cs[i] == '?') {
cs[i] = (char) (t[j++] + 'a');
}
}
return new String(cs);
}
}
// Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
func minimizeStringValue(s string) string {
cnt := [26]int{}
k := 0
for _, c := range s {
if c == '?' {
k++
} else {
cnt[c-'a']++
}
}
pq := hp{}
for i, c := range cnt {
heap.Push(&pq, pair{c, i})
}
t := make([]int, k)
for i := 0; i < k; i++ {
p := heap.Pop(&pq).(pair)
t[i] = p.c
p.v++
heap.Push(&pq, p)
}
sort.Ints(t)
cs := []byte(s)
j := 0
for i, c := range cs {
if c == '?' {
cs[i] = byte(t[j] + 'a')
j++
}
}
return string(cs)
}
type pair struct{ v, c int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v || h[i].v == h[j].v && h[i].c < h[j].c }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
# Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
class Solution:
def minimizeStringValue(self, s: str) -> str:
cnt = Counter(s)
pq = [(cnt[c], c) for c in ascii_lowercase]
heapify(pq)
t = []
for _ in range(s.count("?")):
v, c = pq[0]
t.append(c)
heapreplace(pq, (v + 1, c))
t.sort()
cs = list(s)
j = 0
for i, c in enumerate(s):
if c == "?":
cs[i] = t[j]
j += 1
return "".join(cs)
// Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
// class Solution {
// public String minimizeStringValue(String s) {
// int[] cnt = new int[26];
// int n = s.length();
// int k = 0;
// char[] cs = s.toCharArray();
// for (char c : cs) {
// if (c == '?') {
// ++k;
// } else {
// ++cnt[c - 'a'];
// }
// }
// PriorityQueue<int[]> pq
// = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
// for (int i = 0; i < 26; ++i) {
// pq.offer(new int[] {cnt[i], i});
// }
// int[] t = new int[k];
// for (int j = 0; j < k; ++j) {
// int[] p = pq.poll();
// t[j] = p[1];
// pq.offer(new int[] {p[0] + 1, p[1]});
// }
// Arrays.sort(t);
//
// for (int i = 0, j = 0; i < n; ++i) {
// if (cs[i] == '?') {
// cs[i] = (char) (t[j++] + 'a');
// }
// }
// return new String(cs);
// }
// }
// Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3081: Replace Question Marks in String to Minimize Its Value
// class Solution {
// public String minimizeStringValue(String s) {
// int[] cnt = new int[26];
// int n = s.length();
// int k = 0;
// char[] cs = s.toCharArray();
// for (char c : cs) {
// if (c == '?') {
// ++k;
// } else {
// ++cnt[c - 'a'];
// }
// }
// PriorityQueue<int[]> pq
// = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
// for (int i = 0; i < 26; ++i) {
// pq.offer(new int[] {cnt[i], i});
// }
// int[] t = new int[k];
// for (int j = 0; j < k; ++j) {
// int[] p = pq.poll();
// t[j] = p[1];
// pq.offer(new int[] {p[0] + 1, p[1]});
// }
// Arrays.sort(t);
//
// for (int i = 0, j = 0; i < n; ++i) {
// if (cs[i] == '?') {
// cs[i] = (char) (t[j++] + 'a');
// }
// }
// return new String(cs);
// }
// }
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.