Watch 10 video solutions for Replace Question Marks in String to Minimize Its Value, a medium level problem involving Hash Table, String, Greedy. This walkthrough by Aryan Mittal has 2,115 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given a string containing lowercase letters and ?. Replace every ? with a lowercase character so the total value of the string is minimized. The value increases when the same character appears multiple times, so the goal is to distribute characters as evenly as possible while also returning the lexicographically smallest valid result.
Approach 1: Greedy with Min Heap / Set (Time: O(n log 26), Space: O(26))
This method treats the problem as a frequency balancing task. First count the frequency of existing characters using a small array or a hash table. Maintain a min-heap (or ordered set) of pairs (frequency, character). For every ?, extract the character with the smallest current frequency and assign it. After assignment, increment its frequency and push it back into the heap. This greedy rule works because adding the least-used character minimizes the incremental value cost. Once all replacements are chosen, sort the selected characters before placing them into the ? positions to ensure the lexicographically smallest result. The approach uses ideas from greedy algorithms and priority queues.
Approach 2: Optimized Greedy with Constant Space (Time: O(n), Space: O(1))
The heap is unnecessary because there are only 26 lowercase letters. Instead, maintain a fixed count[26] array using a counting technique. Scan the string once to compute current frequencies and count how many ? exist. For each replacement, linearly check the 26 letters and choose the one with the smallest frequency. Since the alphabet size is constant, this step is effectively O(1). Store the chosen characters, increment their counts, then sort this list before inserting them back into the original string. This produces the same balanced distribution as the heap approach but avoids the log factor and extra data structure.
Recommended for interviews: The greedy strategy is the key insight interviewers expect. Showing the heap-based solution demonstrates you understand how to repeatedly select the minimum-frequency character. The optimized constant-space version is typically preferred in a final solution because the alphabet size is fixed, reducing complexity to O(n) while keeping the implementation simple.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Min Heap / Set | O(n log 26) | O(26) | General greedy implementation when repeatedly selecting the least frequent character |
| Optimized Greedy with Counting | O(n) | O(1) | Best approach when alphabet size is fixed (26 letters) and memory efficiency matters |