Replace Question Marks in String to Minimize Its Value - Solution & Explanation
Problem Statement
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- Hence, the value of
"aab"is0 + 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'?'.
Approach Overview
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 1: Greedy Approach with Set
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.
Complexity
Time Complexity: O(n * 26), where n is the length of the string. Space Complexity: O(26) for storing character usage.
Approach 2: Optimized Greedy Approach with Constant Space
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.
Complexity
Time Complexity: O(n), Space Complexity: O(26) due to fixed alphabets tracking.
Approach 3: Greedy + Priority Queue
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.
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3081. Replace Question Marks in String to Minimize Its Value | Priority Queue | Min Heap | Multiset • Aryan Mittal • 2,142 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Replace Question Marks in String to Minimize Its Value easy or hard?
Replace Question Marks in String to Minimize Its Value Python/Java solution
How to solve Replace Question Marks in String to Minimize Its Value in O(n)?
What is the best approach for Replace Question Marks in String to Minimize Its Value?
Is Replace Question Marks in String to Minimize Its Value asked at Google/Amazon/Meta?
What data structure is used in Replace Question Marks in String to Minimize Its Value?
What is the time complexity of Replace Question Marks in String to Minimize Its Value?
Ready to solve this problem?
Practice Replace Question Marks in String to Minimize Its Value with our built-in code editor and test cases.
Practice on FleetCode