Problem Description

You are given a string s where each character is either a lowercase English letter or a question mark '?'.

For any string t containing only lowercase English letters, we define a cost function for each position. The cost(i) at position i equals the number of times the character t[i] appears before position i (in the range [0, i-1]). The total value of string t is the sum of all cost(i) values.

For example, with string t = "aab":

• cost(0) = 0 (no characters before index 0)
• cost(1) = 1 (one 'a' appears before index 1)
• cost(2) = 0 (no 'b' appears before index 2)
• Total value = 0 + 1 + 0 = 1

Your task is to replace all question marks '?' in string s with lowercase English letters to minimize the total value of the resulting string. If multiple solutions yield the same minimum value, return the lexicographically smallest one.

The key insight is that when a character appears multiple times, it contributes an increasing cost. If a character c appears v times total, its contribution to the overall value is 0 + 1 + 2 + ... + (v-1) = v × (v-1) / 2. To minimize this, we should distribute characters as evenly as possible among the question mark positions.

The solution uses a greedy approach with a min-heap to track character frequencies. For each question mark, we select the character with the lowest current frequency, ensuring balanced distribution. After determining which characters to use, we sort them alphabetically and assign them to question marks in order, guaranteeing the lexicographically smallest result among all minimum-value solutions.

Intuition

The key observation is understanding how the cost accumulates. When a character appears multiple times in a string, each subsequent occurrence adds to the total cost based on how many times it has appeared before. This creates a quadratic growth pattern - the more times a character appears, the more expensive it becomes.

Think of it like stacking identical blocks. The first block costs nothing (cost = 0), the second block costs 1 (one block beneath it), the third costs 2, and so on. If we stack 5 'a' blocks, the total cost is 0 + 1 + 2 + 3 + 4 = 10. But if we split them into 3 'a' blocks and 2 'b' blocks, the cost becomes (0 + 1 + 2) + (0 + 1) = 4, which is much lower.

This leads us to the greedy insight: to minimize the total cost, we should keep the frequency of all characters as balanced as possible. It's better to have multiple characters appear twice than to have one character appear four times.

When we encounter question marks, we should replace them with the characters that currently have the lowest frequency. This prevents any single character from becoming too frequent and expensive. A min-heap (priority queue) is perfect for this - it always gives us the character with the smallest count.

However, there's a catch with the lexicographical requirement. If multiple replacements yield the same minimum cost, we need the alphabetically smallest result. We can't just greedily assign 'a' to the first question mark if we encounter it. Instead, we first determine which characters to use (maintaining minimum cost), collect them, sort them alphabetically, and then assign them to the question marks in order. This two-phase approach ensures both optimal cost and lexicographical ordering.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a greedy strategy using a min-heap to track character frequencies:

Step 1: Count existing characters First, we count the frequency of all characters in the string s using a Counter. This gives us the initial distribution of characters, including any existing lowercase letters.

Step 2: Initialize the priority queue We create a min-heap with tuples (count, character) for all 26 lowercase letters. The heap is ordered by count first, then by character (for tie-breaking). This ensures we always get the character with the minimum frequency, and among those with equal frequency, the lexicographically smallest one.

pq = [(cnt[c], c) for c in ascii_lowercase]
heapify(pq)

Step 3: Determine which characters to use For each question mark in the string, we:

• Extract the character with minimum frequency from the heap
• Add this character to our replacement list t
• Increment its count and put it back in the heap using heapreplace

for _ in range(s.count("?")):
    v, c = pq[0]  # Get min frequency character
    t.append(c)   # Record this character
    heapreplace(pq, (v + 1, c))  # Update count and reinsert

Step 4: Sort for lexicographical order After determining all replacement characters, we sort the list t. This crucial step ensures that when we assign characters to question marks from left to right, we get the lexicographically smallest result among all minimum-cost solutions.

t.sort()

Step 5: Replace question marks Finally, we traverse the original string and replace each question mark with characters from our sorted list t in order:

cs = list(s)
j = 0
for i, c in enumerate(s):
    if c == "?":
        cs[i] = t[j]
        j += 1
return "".join(cs)

The time complexity is O(n log 26 + n log n) where n is the number of question marks, simplifying to O(n log n). The space complexity is O(n) for storing the replacement characters.

Example Walkthrough

Let's walk through the solution with s = "a?b??":

Initial Setup:

• Count existing characters: {'a': 1, 'b': 1}, all others have count 0
• We have 3 question marks to replace

Step 1: Initialize the min-heap Create heap with all 26 letters and their counts:

[(0, 'c'), (0, 'd'), ..., (0, 'z'), (1, 'a'), (1, 'b')]

After heapification, smallest counts are at the top.

Step 2: Determine replacement characters For each of the 3 question marks:

First question mark:

• Extract min: (0, 'c') - 'c' has count 0
• Add 'c' to replacement list: t = ['c']
• Update heap with (1, 'c')

Second question mark:

• Extract min: (0, 'd') - 'd' has count 0
• Add 'd' to replacement list: t = ['c', 'd']
• Update heap with (1, 'd')

Third question mark:

• Extract min: (0, 'e') - 'e' has count 0
• Add 'e' to replacement list: t = ['c', 'd', 'e']
• Update heap with (1, 'e')

Step 3: Sort for lexicographical order t = ['c', 'd', 'e'] (already sorted in this case)

Step 4: Replace question marks left to right

• Position 1: ? → 'c'
• Position 3: ? → 'd'
• Position 4: ? → 'e'

Final Result: "acbde"

Cost Verification:

• 'a' at position 0: cost = 0
• 'c' at position 1: cost = 0 (no 'c' before)
• 'b' at position 2: cost = 0 (no 'b' before)
• 'd' at position 3: cost = 0 (no 'd' before)
• 'e' at position 4: cost = 0 (no 'e' before)
• Total cost = 0

By using different characters for each question mark, we achieved the minimum possible cost while maintaining lexicographical order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log 26) which simplifies to O(n)

The analysis breaks down as follows:

• Counter(s): O(n) where n is the length of string s
• Creating the priority queue with 26 lowercase letters: O(26) = O(1)
• heapify(pq): O(26) = O(1) since the heap has constant size 26
• s.count("?"): O(n)
• The loop that processes question marks: runs k times where k is the number of "?" in s (at most n). Each iteration performs heapreplace which is O(log 26) = O(1). Total: O(k) = O(n)
• t.sort(): O(k × log k) where k is the number of "?". In worst case: O(n × log n)
• Converting to list and back to string: O(n)

The dominant operation is sorting t, giving us O(n × log n) overall time complexity.

Space Complexity: O(n)

The space usage includes:

• cnt Counter: O(26) = O(1) for storing counts of 26 letters
• pq heap: O(26) = O(1)
• t list: O(k) where k is the number of "?" marks, at most O(n)
• cs list: O(n) for storing the character list
• Final string join: O(n)

The dominant space usage is from the list cs and the final string, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Sorting the Replacement Characters

A critical mistake is forgetting to sort the replacement characters before assigning them to question marks. Without sorting, you might achieve the minimum total value but not the lexicographically smallest result.

Incorrect approach:

# Wrong: Using characters directly without sorting
replacement_chars = []
for _ in range(num_questions):
    freq, char = min_heap[0]
    replacement_chars.append(char)
    heapreplace(min_heap, (freq + 1, char))

# Directly replacing without sort
for i, char in enumerate(s):
    if char == "?":
        result_chars[i] = replacement_chars[replacement_index]
        replacement_index += 1

Why it fails: If the string is "a?b?" and the heap gives us ['c', 'a'], we'd get "acba" instead of the lexicographically smaller "aabc".

Solution: Always sort the replacement characters before assignment:

replacement_chars.sort()  # Critical step!

Pitfall 2: Incorrectly Calculating Initial Character Frequencies

Another common error is only counting lowercase letters and ignoring question marks when initializing the frequency counter.

Incorrect approach:

# Wrong: Only counting lowercase letters
char_count = Counter()
for c in s:
    if c != '?':
        char_count[c] += 1

Why it seems wrong but isn't: Actually, this works fine because Counter in Python returns 0 for missing keys. However, explicitly handling this can lead to confusion.

Better approach: Use Counter directly on the entire string:

char_count = Counter(s)
# Question marks are counted but won't affect lowercase letter frequencies

Pitfall 3: Using Wrong Heap Comparison

When multiple characters have the same frequency, failing to break ties lexicographically in the heap can lead to incorrect character selection.

Incorrect approach:

# Wrong: Only considering frequency
min_heap = [(char_count[char],) for char in ascii_lowercase]
# This doesn't guarantee lexicographical order for ties

Solution: Include the character itself in the tuple for proper tie-breaking:

min_heap = [(char_count[char], char) for char in ascii_lowercase]
# Python's heap will use character for tie-breaking automatically

Pitfall 4: Modifying String In-Place

Attempting to modify the string directly instead of converting to a list first.

Incorrect approach:

# Wrong: Strings are immutable in Python
for i, char in enumerate(s):
    if char == "?":
        s[i] = replacement_chars[replacement_index]  # Error!

Solution: Convert to list, modify, then join:

result_chars = list(s)
for i, char in enumerate(s):
    if char == "?":
        result_chars[i] = replacement_chars[replacement_index]
        replacement_index += 1
return "".join(result_chars)