Replace Question Marks in String to Minimize Its Value

Med

#2737Time: O(N + q * A + q log q), where N is the length of the string, q is the number of '?', and A is the alphabet size (26). The initial scan of the string is O(N). Determining the `q` replacement characters takes `q` iterations, with each iteration scanning `A` characters, totaling O(q * A). Sorting the replacements takes O(q log q). Building the final string takes O(N). Since A is a constant, the complexity simplifies to O(N + q log q).Space: O(N + A), where N is the length of the string and A is the alphabet size (26). This is because we store the indices of '?' (up to O(N)), the replacement characters (up to O(N)), and the character counts (O(A)). If we consider the output string as part of the complexity, it's O(N). The auxiliary space is O(q + A), where q is the number of question marks.

Patterns

Greedy Counting

Algorithms

Sorting

Data structures

Hash Table String Heap (Priority Queue)

Prompt

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.

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 <= 10⁵
s[i] is either a lowercase English letter or '?'.

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea behind solving this problem is to understand how the 'value' of a string is calculated. The value is the sum of k*(k-1)/2 for each character, where k is its total count. To minimize this sum, we need to keep the character counts as balanced as possible. This suggests a greedy strategy.

We have a number of '?'s to replace, say q. For each replacement, we should choose a character that results in the smallest possible increase in the total value. The marginal increase in value when adding an instance of a character c that already appears k times is k. Therefore, at each step, we should greedily choose the character with the current minimum frequency.

To handle the secondary requirement of returning the lexicographically smallest string, we apply two rules:

When determining the set of q characters to use for replacement, if there's a tie in minimum frequency (e.g., 'b' and 'c' both appear 0 times), we choose the lexicographically smaller character ('b'). This makes the multiset of replacement characters itself lexicographically smaller.
After determining this multiset, we sort these characters and place them into the '?' positions from left to right. This ensures the final string is as small as possible.

This approach implements the greedy strategy by repeatedly scanning through all 26 alphabet characters to find the one with the minimum current frequency.

Algorithm

Count Frequencies and '?'s:
1. Create an integer array counts of size 26, initialized to zero, to store the frequencies of characters 'a' through 'z'.
2. Create a list q_indices to store the original indices of the '?' characters.
3. Iterate through the input string s from left to right. For each character:
  - If it's a letter, increment the corresponding counter in the counts array.
  - If it's a '?', add its index to q_indices.
Determine Replacement Characters:
1. Let q be the number of '?'s (the size of q_indices).
2. Create a list of characters called replacements.
3. Loop q times to decide which character to use for each '?': a. Initialize min_count to a very large value and char_to_add to a placeholder. b. Iterate through all characters from 'a' to 'z'. In this inner loop, find the character that has the minimum count in the counts array. If multiple characters share the same minimum count, the one that comes first alphabetically is chosen due to the loop's order. c. Add the chosen character (char_to_add) to the replacements list. d. Increment the count of char_to_add in the counts array to reflect its addition.
Construct the Final String:
1. Sort the replacements list in alphabetical order.
2. Convert the input string s into a character array s_chars for easy modification.
3. Iterate q times. In each iteration i, take the i-th index from q_indices and the i-th character from the sorted replacements list, and place the character at that index in s_chars.
4. Convert s_chars back to a string and return it.

Walkthrough

1class Solution {2    public String minimizeStringValue(String s) {3        int[] counts = new int[26];4        List<Integer> qIndices = new ArrayList<>();5        for (int i = 0; i < s.length(); i++) {6            char c = s.charAt(i);7            if (c == '?') {8                qIndices.add(i);9            } else {10                counts[c - 'a']++;11            }12        }13 14        int q = qIndices.size();15        if (q == 0) {16            return s;17        }18 19        List<Character> replacements = new ArrayList<>();20        for (int i = 0; i < q; i++) {21            int minCount = Integer.MAX_VALUE;22            char charToUse = ' ';23            // Find char with min count, breaking ties lexicographically24            for (char c = 'a'; c <= 'z'; c++) {25                if (counts[c - 'a'] < minCount) {26                    minCount = counts[c - 'a'];27                    charToUse = c;28                }29            }30            replacements.add(charToUse);31            counts[charToUse - 'a']++;32        }33 34        Collections.sort(replacements);35 36        char[] sChars = s.toCharArray();37        for (int i = 0; i < q; i++) {38            sChars[qIndices.get(i)] = replacements.get(i);39        }40 41        return new String(sChars);42    }43}

Complexity

Time

O(N + q * A + q log q), where N is the length of the string, q is the number of '?', and A is the alphabet size (26). The initial scan of the string is O(N). Determining the `q` replacement characters takes `q` iterations, with each iteration scanning `A` characters, totaling O(q * A). Sorting the replacements takes O(q log q). Building the final string takes O(N). Since A is a constant, the complexity simplifies to O(N + q log q).

Space

O(N + A), where N is the length of the string and A is the alphabet size (26). This is because we store the indices of '?' (up to O(N)), the replacement characters (up to O(N)), and the character counts (O(A)). If we consider the output string as part of the complexity, it's O(N). The auxiliary space is O(q + A), where q is the number of question marks.

Trade-offs

Pros

The approach is relatively straightforward to understand and implement.
It correctly minimizes the string's value and produces the lexicographically smallest result among optimal solutions.

Cons

The process of finding the character with the minimum frequency involves a linear scan through all 26 characters for each of the q question marks. This is less efficient than using a data structure optimized for finding minimums, such as a priority queue.

This approach is an optimization of the previous greedy method. The fundamental logic of minimizing value by balancing character counts and ensuring lexicographical order remains the same. The key difference lies in how we efficiently find the character with the minimum frequency at each step.

Instead of a linear scan through all 26 characters for each of the q replacements, we use a min-priority queue. The priority queue is a data structure specifically designed to provide quick access to the minimum (or maximum) element. By storing the character frequencies in a priority queue, we can retrieve the best character to add in O(log A) time, where A is the alphabet size.

We configure the priority queue to order elements first by frequency, and then by character value for tie-breaking. This ensures we always pick the character that minimizes the value cost, and among those, the one that leads to a lexicographically smaller set of replacement characters. This makes the process of determining the q replacement characters significantly faster, especially when q is large.

Algorithm

Count Frequencies and '?'s:
1. This step is identical to the previous approach. We calculate initial character counts and find all q_indices.
Setup Priority Queue:
1. Create a min-priority queue. This queue will store elements representing each character and its frequency.
2. The elements can be pairs or a small array like [frequency, character_index].
3. The priority queue must be configured with a custom comparator to order elements first by frequency (ascending), and then by character_index (ascending) to break ties.
4. Populate the priority queue by adding an entry for each of the 26 characters with its initial count from the counts array.
Determine Replacement Characters:
1. Let q be the number of '?'s.
2. Create a list of characters called replacements.
3. Loop q times: a. Extract the element with the highest priority (lowest frequency, then lowest character value) from the priority queue. Let this be (freq, char_idx). b. Add the corresponding character to the replacements list. c. Insert a new element (freq + 1, char_idx) back into the priority queue to update the character's frequency for subsequent steps.
Construct the Final String:
1. This step is also identical to the previous approach. Sort the replacements list and fill in the '?' positions in the original string.

Walkthrough

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4import java.util.PriorityQueue;5 6class Solution {7    public String minimizeStringValue(String s) {8        int[] counts = new int[26];9        List<Integer> qIndices = new ArrayList<>();10        for (int i = 0; i < s.length(); i++) {11            char c = s.charAt(i);12            if (c == '?') {13                qIndices.add(i);14            } else {15                counts[c - 'a']++;16            }17        }18 19        int q = qIndices.size();20        if (q == 0) {21            return s;22        }23 24        // PriorityQueue stores pairs of [count, character_index]25        // It's a min-heap, ordered by count, then by character_index26        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {27            if (a[0] != b[0]) {28                return a[0] - b[0];29            }30            return a[1] - b[1];31        });32 33        for (int i = 0; i < 26; i++) {34            pq.offer(new int[]{counts[i], i});35        }36 37        List<Character> replacements = new ArrayList<>();38        for (int i = 0; i < q; i++) {39            int[] top = pq.poll();40            char charToUse = (char) ('a' + top[1]);41            replacements.add(charToUse);42            top[0]++;43            pq.offer(top);44        }45 46        Collections.sort(replacements);47 48        char[] sChars = s.toCharArray();49        for (int i = 0; i < q; i++) {50            sChars[qIndices.get(i)] = replacements.get(i);51        }52 53        return new String(sChars);54    }55}

Complexity

Time

O(N + A log A + q log A + q log q). The initial scan is O(N). Building the priority queue of size A takes O(A log A). The main loop runs `q` times, with each poll/offer operation taking O(log A), for a total of O(q log A). Sorting replacements is O(q log q). As A is a small constant (26), `log A` is also a small constant. The dominant terms are O(N + q log q).

Space

O(N + A), where N is the string length and A is the alphabet size. The auxiliary space complexity is O(q + A) for storing `q_indices`, `replacements`, `counts`, and the priority queue.

Trade-offs

Pros

Highly efficient, as it uses the optimal data structure (priority queue) for repeatedly finding the minimum element.
Provides the optimal solution in terms of both value and lexicographical order.
The time complexity is better than the linear scan approach for the character selection part.

Cons

The implementation is slightly more complex due to the use of a PriorityQueue with a custom comparator.

Solutions

Solution

1class Solution {2public3  String minimizeStringValue(String s) {4    int[] cnt = new int[26];5    int n = s.length();6    int k = 0;7    char[] cs = s.toCharArray();8    for (char c : cs) {9      if (c == '?') {10        ++k;11      } else {12        ++cnt[c - 'a'];13      }14    }15    PriorityQueue<int[]> pq =16        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);17    for (int i = 0; i < 26; ++i) {18      pq.offer(new int[]{cnt[i], i});19    }20    int[] t = new int[k];21    for (int j = 0; j < k; ++j) {22      int[] p = pq.poll();23      t[j] = p[1];24      pq.offer(new int[]{p[0] + 1, p[1]});25    }26    Arrays.sort(t);27    for (int i = 0, j = 0; i < n; ++i) {28      if (cs[i] == '?') {29        cs[i] = (char)(t[j++] + 'a');30      }31    }32    return new String(cs);33  }34}

1class Solution {2public:3  string minimizeStringValue(string s) {4    int cnt[26]{};5    int k = 0;6    for (char &c : s) {7      if (c == '?') {8        ++k;9      } else {10        ++cnt[c - 'a'];11      }12    }13    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;14    for (int i = 0; i < 26; ++i) {15      pq.push({cnt[i], i});16    }17    vector<int> t(k);18    for (int i = 0; i < k; ++i) {19      auto [v, c] = pq.top();20      pq.pop();21      t[i] = c;22      pq.push({v + 1, c});23    }24    sort(t.begin(), t.end());25    int j = 0;26    for (char &c : s) {27      if (c == '?') {28        c = t[j++] + 'a';29      }30    }31    return s;32  }33};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem