LeetCode 3081 - Replace Question Marks in String to Minimize Its Value

The problem gives us a string s containing lowercase English letters and the character '?'. Every '?' must be replaced with a lowercase letter so that the resulting string has the minimum possible value.

leetcodemediumhash-tablestringgreedysortingheap-(priority-queue)counting

LeetCode Problem 3081

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting

Solution

Problem Understanding

The problem gives us a string s containing lowercase English letters and the character '?'. Every '?' must be replaced with a lowercase letter so that the resulting string has the minimum possible value.

The value of a string is determined by counting repeated occurrences of letters. For every position i, cost(i) equals the number of times the same character has already appeared earlier in the string.

For example, in "aab":

  • The first 'a' has no previous 'a', so its contribution is 0
  • The second 'a' has one previous 'a', so its contribution is 1
  • The 'b' has no previous 'b', so its contribution is 0

The total value becomes 1.

We are allowed to replace each '?' with any lowercase English letter. Among all possible strings with the minimum value, we must return the lexicographically smallest one.

The key observation is that every additional occurrence of a letter increases the total value. If a letter already appeared k times, adding one more occurrence contributes k to the value. Therefore, repeatedly choosing letters with the smallest current frequency minimizes the total cost.

The constraints are important:

  • 1 <= s.length <= 10^5
  • Only lowercase English letters exist

The string can be very large, so exponential or quadratic approaches are impossible. However, there are only 26 possible letters, which strongly suggests that greedy counting techniques are feasible.

Several edge cases are important:

  • A string containing only '?'
  • A string with no '?'
  • A string where almost all letters are already heavily repeated
  • Multiple optimal solutions where lexicographical order decides the answer

A naive implementation can easily minimize the value but fail to produce the lexicographically smallest valid answer.

Approaches

Brute Force Approach

A brute force solution would try every possible replacement for each '?'.

If the string contains k question marks, then there are 26^k possible strings. For every generated string, we could compute its value by counting previous occurrences of each character.

This guarantees correctness because every possible replacement is explored, and we choose the valid string with minimum value and smallest lexicographical order.

However, this approach is completely infeasible. Even for k = 20, the number of possibilities becomes enormous:

$$26^{20}$$

The input size can reach 10^5, so brute force is impossible.

Optimal Greedy Approach

The crucial observation is that the contribution of adding another occurrence of a letter depends only on how many times that letter already appeared.

If a letter currently appeared f times, then placing it again increases the total value by f.

Therefore, to minimize the total value:

  • Always choose the character with the smallest current frequency
  • If multiple characters have the same frequency, prefer the lexicographically smaller one

This becomes a greedy balancing problem.

We first count frequencies of all existing letters. Then, for every '?', we choose the letter with the smallest frequency. After choosing it, we increment its count.

However, directly placing characters greedily from left to right does not always guarantee the lexicographically smallest final string. To solve this correctly:

  1. Determine all replacement letters greedily
  2. Sort those chosen letters
  3. Fill the '?' positions from left to right using the sorted letters

This preserves the minimum value while ensuring the smallest lexicographical order.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(26^k * n) O(n) Tries every replacement combination
Optimal O(n + k log k) O(k) Greedy frequency balancing with lexicographical optimization

Here, k is the number of '?' characters.

Algorithm Walkthrough

  1. Count the frequency of every existing lowercase letter in the string.

We use an array of size 26 because there are only 26 lowercase English letters. This allows constant time frequency updates and lookups. 2. Traverse the string and process every '?'.

For each '?', find the character with the smallest current frequency.

If multiple characters share the same minimum frequency, choose the lexicographically smallest one.

This greedy choice minimizes the added contribution to the string value. 3. Store the selected replacement characters.

We do not immediately place them into the string. Instead, we collect them in a separate list. 4. Increment the frequency of the chosen character.

This reflects the fact that the character is now considered used for future decisions. 5. Sort the collected replacement characters.

This step is essential for lexicographical minimization.

The greedy process determines only how many times each character should be used. Their exact placement among the '?' positions can still vary.

Sorting ensures the smallest letters appear earlier in the string. 6. Traverse the string again and replace each '?'.

Fill the positions from left to right using the sorted replacement list. 7. Return the final string.

Why it works

The greedy strategy works because every additional occurrence of a character increases the total value by exactly its current frequency. Choosing the minimum frequency character at every step always produces the smallest possible incremental cost.

Sorting the selected replacement characters afterward does not change the frequency distribution, so the total value remains minimal. It only improves lexicographical order by placing smaller characters earlier.

Therefore, the algorithm simultaneously guarantees:

  • Minimum possible value
  • Lexicographically smallest result among all optimal solutions

Python Solution

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        frequency = [0] * 26
        
        for ch in s:
            if ch != '?':
                frequency[ord(ch) - ord('a')] += 1
        
        replacements = []
        
        for ch in s:
            if ch == '?':
                best_index = 0
                
                for i in range(26):
                    if frequency[i] < frequency[best_index]:
                        best_index = i
                
                replacements.append(chr(best_index + ord('a')))
                frequency[best_index] += 1
        
        replacements.sort()
        
        result = list(s)
        replacement_index = 0
        
        for i in range(len(result)):
            if result[i] == '?':
                result[i] = replacements[replacement_index]
                replacement_index += 1
        
        return ''.join(result)

The implementation begins by counting frequencies of all existing letters. Since only lowercase English letters exist, an array of size 26 is sufficient and very efficient.

Next, the code processes every '?'. For each one, it scans all 26 letters and selects the letter with the smallest frequency. Because the scan occurs from 'a' to 'z', ties automatically favor lexicographically smaller letters.

The chosen characters are stored inside replacements, and their frequencies are updated immediately so future decisions remain correct.

After all replacements are determined, the list is sorted. This ensures lexicographical minimality.

Finally, the string is converted into a mutable list, and each '?' is replaced using the sorted replacement letters.

The resulting string is joined and returned.

Go Solution

func minimizeStringValue(s string) string {
	frequency := make([]int, 26)

	for _, ch := range s {
		if ch != '?' {
			frequency[ch-'a']++
		}
	}

	replacements := make([]byte, 0)

	for _, ch := range s {
		if ch == '?' {
			bestIndex := 0

			for i := 0; i < 26; i++ {
				if frequency[i] < frequency[bestIndex] {
					bestIndex = i
				}
			}

			replacements = append(replacements, byte(bestIndex+'a'))
			frequency[bestIndex]++
		}
	}

	sort.Slice(replacements, func(i, j int) bool {
		return replacements[i] < replacements[j]
	})

	result := []byte(s)
	index := 0

	for i := 0; i < len(result); i++ {
		if result[i] == '?' {
			result[i] = replacements[index]
			index++
		}
	}

	return string(result)
}

The Go implementation follows the same logic as the Python version.

The main difference is that Go strings are immutable, so the string is converted into a byte slice before replacements are performed.

The sort.Slice function is used to sort replacement characters lexicographically.

No integer overflow concerns exist because frequencies never exceed 10^5.

Worked Examples

Example 1

Input:

s = "???"

Initial frequencies:

Letter Count
a-z 0

Step 1: Process first '?'

All letters have frequency 0.

Choose 'a'.

Updated frequencies:

Letter Count
a 1

Replacements:

['a']

Step 2: Process second '?'

Smallest frequency letters are now 'b' through 'z'.

Choose 'b'.

Updated frequencies:

Letter Count
a 1
b 1

Replacements:

['a', 'b']

Step 3: Process third '?'

Choose 'c'.

Replacements:

['a', 'b', 'c']

Sorted replacements:

['a', 'b', 'c']

Final string:

"abc"

Example 2

Input:

s = "a?a?"

Initial frequencies:

Letter Count
a 2

Step 1: Process first '?'

Current minimum frequency is 0.

Choose 'b'.

Replacements:

['b']

Updated frequencies:

Letter Count
a 2
b 1

Step 2: Process second '?'

Current minimum frequency is 0.

Choose 'c'.

Replacements:

['b', 'c']

Sorted replacements:

['b', 'c']

Fill into string:

Position Character
0 a
1 b
2 a
3 c

Final string:

"abac"

Complexity Analysis

Measure Complexity Explanation
Time O(n + k log k) Counting and scanning are linear, sorting replacements dominates
Space O(k) Stores replacement characters

Here, n is the string length and k is the number of '?' characters.

The frequency scan for each '?' examines only 26 letters, which is constant time. Therefore, processing all characters remains linear overall. The sorting step costs O(k log k).

Test Cases

solution = Solution()

assert solution.minimizeStringValue("???") == "abc"  # all question marks
assert solution.minimizeStringValue("a?a?") == "abac"  # mix of fixed and unknown
assert solution.minimizeStringValue("abc") == "abc"  # no replacements needed
assert solution.minimizeStringValue("?") == "a"  # single character
assert solution.minimizeStringValue("zz?") == "zza"  # choose least used letter
assert solution.minimizeStringValue("abcdefghijklmnopqrstuvwxy?") == "abcdefghijklmnopqrstuvwxyz"  # only z missing
assert solution.minimizeStringValue("??????????????????????????") == "abcdefghijklmnopqrstuvwxyz"  # all unique letters
assert solution.minimizeStringValue("aa??") == "aabc"  # avoid increasing existing duplicates
assert solution.minimizeStringValue("b?a?") == "bcad"  # lexicographical ordering matters
assert solution.minimizeStringValue("cccc????") == "ccccabde"  # distribute frequencies evenly

Test Summary

Test Why
"???" Verifies all unknown characters
"a?a?" Checks mixed fixed and unknown positions
"abc" Ensures unchanged strings work correctly
"?" Smallest possible input
"zz?" Ensures low frequency letters are preferred
"abcdefghijklmnopqrstuvwxy?" Verifies missing final letter handling
"??????????????????????????" Tests full alphabet balancing
"aa??" Ensures duplicate minimization
"b?a?" Tests lexicographical ordering
"cccc????" Validates balanced greedy assignment

Edge Cases

String Contains No Question Marks

If the input string already contains only lowercase letters, the algorithm should return the original string unchanged.

This can easily cause bugs if the implementation assumes at least one replacement exists. In this solution, the replacements list simply remains empty, and the second traversal performs no modifications.

String Contains Only Question Marks

When every character is '?', the optimal solution is to distribute characters as evenly as possible.

For example, "???" becomes "abc" rather than "aaa" because repeated letters increase the value. The greedy frequency balancing naturally produces distinct letters first.

Existing Characters Are Highly Repeated

Consider a string like "zzzz??".

A naive implementation might continue using 'z', which would heavily increase the value. The correct approach instead chooses letters with smaller frequencies, such as 'a' and 'b'.

The greedy frequency comparison guarantees that already frequent letters are avoided whenever possible.

Multiple Optimal Answers Exist

Several different strings can produce the same minimum value.

For example:

"???"

Both "abc" and "cba" achieve value 0.

The problem requires the lexicographically smallest valid answer. Sorting the selected replacement characters before insertion guarantees this property.