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.
This approach involves iterating through the string and replacing '?' with the smallest possible character that ensures the lexicographical order is upheld. We use a set to maintain previously seen characters to ensure minimal cost calculation.
This solution iterates through the string, using a set (an array of booleans) to track which characters are available to replace '?'. The replacement is done in a way that minimizes value and preserves lexical order.
Time Complexity: O(n * 26), where n is the length of the string. Space Complexity: O(26) for storing character usage.
This approach is an optimized variant of the greedy method. By minimizing the use of extra space, it modifies the string in place and maintains an array to track the last seen position of each character, leading to reduced cost and minimal space usage.
C implementation optimizes space by using an integer array to track the last seen position of characters. This helps avoid repetitive occurrence and ensures minimal cost.
Time Complexity: O(n), Space Complexity: O(26) due to fixed alphabets tracking.
According to the problem, we can find that if a letter c appears v times, then the score it contributes to the answer is 1 + 2 + cdots + (v - 1) = \frac{v times (v - 1)}{2}. To make the answer as small as possible, we should replace the question marks with those letters that appear less frequently.
Therefore, we can use a priority queue to maintain the occurrence times of each letter, take out the letter with the least occurrence times each time, record it in the array t, then increase its occurrence times by one, and put it back into the priority queue. Finally, we sort the array t, and then traverse the string s, replacing each question mark with the letters in the array t in turn.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Greedy Approach with Set | Time Complexity: O(n * 26), where n is the length of the string. Space Complexity: O(26) for storing character usage. |
| Optimized Greedy Approach with Constant Space | Time Complexity: O(n), Space Complexity: O(26) due to fixed alphabets tracking. |
| Greedy + Priority Queue | — |
| 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 |
3081. Replace Question Marks in String to Minimize Its Value | Priority Queue | Min Heap | Multiset • Aryan Mittal • 2,115 views views
Watch 9 more video solutions →Practice Replace Question Marks in String to Minimize Its Value with our built-in code editor and test cases.
Practice on FleetCode