Replace Question Marks in String to Minimize Its Value solution and explanation
9 more videos on this problem
3081. Replace Question Marks in String to Minimize Its Value | Priority Queue | Min Heap | MultisetAryan Mittal · 30:04 · 2K views
3081. Replace Question Marks in String to Minimize Its Value (Leetcode Medium)Programming Live with Larry · 15:01 · 594 views
Biweekly Contest 126 | Replace Question Marks in String to Minimize Its Value QuestionCodeWithMe21 · 0:46 · 524 views
Leetcode 3081: Replace Question Marks in String to Minimize Its ValueAlgorithms Casts · 15:51 · 316 views
LeetCode | 3081. Replace Question Marks in String to Minimize Its Value | Biweekly Contest 126Coding with Bobby · 5:46 · 226 views
Leetcode 3081 | Replace Question Marks in String to Minimize Its Value | Biweekly Contest 126Road To FAANG · 7:56 · 143 views
3081. Replace Question Marks in String to Minimize Its Value | Leetcode biweekly contest 126 | GeeksGeekstocode · 21:23 · 133 views
3081. Replace Question Marks in String to Minimize Its Value || Leetcode Biweekly Contest 126Ashish Kumar · 25:03 · 86 views
3081. Replace Question Marks in String to Minimize It Value | BW Contest 126 | Intuition | Approach?Code Warehouse · 27:35 · 75 views
3081 Replace Question Marks in String to Minimize Its ValueFullStack · 11:21 · 64 views
The problem
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.
def replace_and_minimize(s: str) -> str:
seen = set(s) - {'?'}
result = list(s)
for i, char in enumerate(result):
if char == '?':
for c in 'abcdefghijklmnopqrstuvwxyz':
if c not in seen or (i > 0 and c == result[i-1]):
continue
result[i] = c
seen.add(c)
break
return ''.join(result)
s = "a?a?"
print(replace_and_minimize(s))import java.util.*;
public class ReplaceQuestions {
public static String replaceAndMinimize(String s) {
Set<Character> seen = new HashSet<>();
char[] result = s.toCharArray();
for (char c : result) {
if (c != '?') seen.add(c);
}
for (int i = 0; i < result.length; i++) {
if (result[i] == '?') {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (!seen.contains(ch) || (i > 0 && ch == result[i-1])) continue;
result[i] = ch;
seen.add(ch);
break;
}
}
}
return new String(result);
}
public static void main(String[] args) {
String s = "a?a?";
System.out.println(replaceAndMinimize(s));
}
}#include <iostream>
#include <string>
#include <unordered_set>
std::string replaceAndMinimize(std::string s) {
std::unordered_set<char> seen;
for (char c : s) {
if (c != '?') seen.insert(c);
}
for (size_t i = 0; i < s.length(); i++) {
if (s[i] == '?') {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (seen.find(ch) == seen.end() || (i > 0 && ch == s[i-1])) continue;
s[i] = ch;
seen.insert(ch);
break;
}
}
}
return s;
}
int main() {
std::string s = "a?a?";
std::cout << replaceAndMinimize(s) << std::endl;
return 0;
}function replaceAndMinimize(s) {
const seen = new Set(s.split('').filter(c => c !== '?'));
const result = s.split('');
for (let i = 0; i < result.length; i++) {
if (result[i] === '?') {
for (let ch of 'abcdefghijklmnopqrstuvwxyz') {
if (seen.has(ch) && (i === 0 || ch !== result[i-1])) {
result[i] = ch;
seen.add(ch);
break;
}
}
}
}
return result.join('');
}
let s = "a?a?";
console.log(replaceAndMinimize(s));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
void replaceAndMinimize(char *s) {
bool seen[26] = {0};
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] != '?') {
seen[s[i] - 'a'] = true;
}
}
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
for (int j = 0; j < 26; j++) {
if (!seen[j] || (i > 0 && j == s[i-1] - 'a')) continue;
s[i] = 'a' + j;
seen[j] = true;
break;
}
}
}
printf("%s\n", s);
}
int main() {
char s[] = "a?a?";
replaceAndMinimize(s);
return 0;
}using System;
using System.Collections.Generic;
class ReplaceQuestions {
public static string ReplaceAndMinimize(string s) {
var seen = new HashSet<char>(s);
char[] result = s.ToCharArray();
for (int i = 0; i < result.Length; i++) {
if (result[i] == '?') {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (!seen.Contains(ch) || (i > 0 && ch == result[i-1])) continue;
result[i] = ch;
seen.Add(ch);
break;
}
}
}
return new string(result);
}
public static void Main() {
string s = "a?a?";
Console.WriteLine(ReplaceAndMinimize(s));
}
}This Python solution manages seen characters with a set. It replaces '?' using a greedy approach that minimizes value and maintains lexical order.
Time Complexity: O(n * 26) due to nested iterations, Space Complexity: O(n) for manipulating string representation.
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.
def replace_minimize(s: str) -> str:
last_pos = [-1] * 26
result = list(s)
for i, ch in enumerate(result):
if ch == '?':
for j in range(26):
if last_pos[j] == -1 or last_pos[j] < i - 1:
result[i] = chr(j + ord('a'))
break
last_pos[ord(result[i]) - ord('a')] = i
return ''.join(result)
s = "a?a?"
print(replace_minimize(s))public class ReplaceMinimize {
public static String replaceMinimize(String s) {
int[] last_pos = new int[26];
for (int i = 0; i < 26; i++) last_pos[i] = -1;
char[] result = s.toCharArray();
for (int i = 0; i < result.length; i++) {
if (result[i] == '?') {
for (int j = 0; j < 26; j++) {
if (last_pos[j] == -1 || last_pos[j] < i - 1) {
result[i] = (char)('a' + j);
break;
}
}
}
last_pos[result[i] - 'a'] = i;
}
return new String(result);
}
public static void main(String[] args) {
String s = "a?a?";
System.out.println(replaceMinimize(s));
}
}#include <iostream>
#include <string>
#include <vector>
std::string replaceMinimize(std::string s) {
std::vector<int> last_pos(26, -1);
for (size_t i = 0; i < s.length(); i++) {
if (s[i] == '?') {
for (int j = 0; j < 26; j++) {
if (last_pos[j] == -1 || last_pos[j] < i - 1) {
s[i] = 'a' + j;
break;
}
}
}
last_pos[s[i] - 'a'] = i;
}
return s;
}
int main() {
std::string s = "a?a?";
std::cout << replaceMinimize(s) << std::endl;
return 0;
}function replaceMinimize(s) {
let last_pos = Array(26).fill(-1);
const result = s.split('');
for (let i = 0; i < result.length; i++) {
if (result[i] === '?') {
for (let j = 0; j < 26; j++) {
if (last_pos[j] === -1 || last_pos[j] < i - 1) {
result[i] = String.fromCharCode('a'.charCodeAt(0) + j);
break;
}
}
}
last_pos[result[i].charCodeAt(0) - 'a'.charCodeAt(0)] = i;
}
return result.join('');
}
let s = "a?a?";
console.log(replaceMinimize(s));#include <stdio.h>
#include <string.h>
void replaceMinimize(char *s) {
int n = strlen(s), last_pos[26] = {-1};
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
for (int j = 0; j < 26; j++) {
if (last_pos[j] == -1 || last_pos[j] < i - 1) {
s[i] = 'a' + j;
break;
}
}
}
last_pos[s[i] - 'a'] = i;
}
printf("%s\n", s);
}
int main() {
char s[] = "a?a?";
replaceMinimize(s);
return 0;
}using System;
class ReplaceMinimize {
public static string ReplaceMinimize(string s) {
int[] last_pos = new int[26];
Array.Fill(last_pos, -1);
char[] result = s.ToCharArray();
for (int i = 0; i < result.Length; i++) {
if (result[i] == '?') {
for (int j = 0; j < 26; j++) {
if (last_pos[j] == -1 || last_pos[j] < i - 1) {
result[i] = (char)('a' + j);
break;
}
}
}
last_pos[result[i] - 'a'] = i;
}
return new string(result);
}
public static void Main() {
string s = "a?a?";
Console.WriteLine(ReplaceMinimize(s));
}
}Python approach optimizes '?' replacements by remembering the last occurrence of characters, favoring minimal cost-efficiency in replacements while maintaining lexical order simplicity.
Time Complexity: O(n), Space Complexity: O(26) representing character space utilization.
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.
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 }Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Set | Time Complexity: O(n * 26) due to nested iterations, Space Complexity: O(n) for manipulating string representation. |
| Optimized Greedy Approach with Constant Space | Time Complexity: O(n), Space Complexity: O(26) representing character space utilization. |
| Greedy + Priority Queue | – |
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 |
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 is generally classified as a Medium difficulty problem. The challenge comes from recognizing the greedy distribution principle and ensuring the lexicographically smallest valid string while minimizing duplicate character costs.
Replace Question Marks in String to Minimize Its Value Python/Java solution
Python and Java solutions typically implement the greedy strategy using either a PriorityQueue/min-heap or a simple frequency array. The algorithm counts existing characters, selects the least frequent letter for each '?', updates the count, and finally inserts the replacements in sorted order to maintain lexicographic minimality.
How to solve Replace Question Marks in String to Minimize Its Value in O(n)?
First count the frequency of each existing letter. For every '?' choose the character with the smallest frequency using a 26-length counting array. Store these chosen letters, update their counts, then sort the replacements before inserting them back into the string. Because the alphabet size is constant, each selection is O(1) and the overall complexity becomes O(n).
What is the best approach for Replace Question Marks in String to Minimize Its Value?
The most effective approach is a greedy frequency-balancing strategy. Track how many times each letter appears and always replace '?' with the character that currently has the smallest frequency. This minimizes the incremental value contributed by duplicates. With a fixed alphabet of 26 letters, the optimized counting approach runs in O(n) time and O(1) space.
Is Replace Question Marks in String to Minimize Its Value asked at Google/Amazon/Meta?
Greedy frequency balancing and string reconstruction problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The exact problem may vary, but the pattern of distributing characters to minimize repetition and using a heap or counting array is common in coding interviews.
What data structure is used in Replace Question Marks in String to Minimize Its Value?
Common implementations use a frequency array combined with a min heap (priority queue). The heap helps repeatedly pick the character with the smallest current count. In optimized solutions, the heap can be replaced by a fixed-size counting array since there are only 26 lowercase letters.
What is the time complexity of Replace Question Marks in String to Minimize Its Value?
The optimal implementation runs in O(n) time where n is the length of the string. Each '?' replacement checks at most 26 characters, which is constant work. Space complexity is O(1) because only a fixed-size frequency array of length 26 is required.