Replace Question Marks in String to Minimize Its Value

Replace Question Marks in String to Minimize Its Value

What is this problem about?

The Replace Question Marks in String to Minimize Its Value interview question gives you a string with lowercase letters and '?' characters. You must replace each '?' with a lowercase letter to minimize the "value" of the string, where value is defined as the sum over all characters of the number of times that character appeared before the current position. In other words, you want to fill wildcards with letters that have appeared as few times as possible up to each point.

Why is this asked in interviews?

Amazon asks this problem because it combines greedy character assignment with frequency tracking using a min-heap. It tests whether candidates can translate an abstract cost function into a concrete greedy strategy and implement it efficiently. The problem rewards structured thinking: sort characters by frequency, always assign the least-used one to minimize the cost.

Algorithmic pattern used

The pattern is greedy with a min-heap (priority queue). First, count the frequency of all existing (non-'?') characters. Build a min-heap of (frequency, character) pairs for all 26 letters. For each '?' position, extract the character with the minimum current frequency, assign it, and push it back with frequency incremented by 1. This greedily minimizes the contribution of each replacement to the total cost.

Example explanation

String: "a?b?"

Existing chars: a=1, b=1. All others=0. Min-heap starts with: (0,'c'), (0,'d'), ..., (1,'a'), (1,'b').

• First '?' (index 1): pop min → (0,'c'). Assign 'c', push (1,'c').
• Second '?' (index 3): pop min → (0,'d'). Assign 'd', push (1,'d').

Result: "acbd". Value contribution minimized by using fresh characters.

Common mistakes candidates make

• Assigning characters greedily based only on global frequency without using a heap, leading to suboptimal assignments.
• Forgetting to sort lexicographically when frequencies tie — using the lexicographically smallest character as a tiebreaker produces the smallest string.
• Not counting existing characters before starting the heap, skewing frequency tracking.
• Replacing '?' characters with only one or two letters when more variety reduces cost.

Interview preparation tip

For the Replace Question Marks in String to Minimize Its Value coding problem, the heap (priority queue), counting, and greedy interview pattern is central. Build the frequency map first, then drive assignments with a min-heap. Amazon interviewers may ask about the tie-breaking rule — using lexicographic order as a tiebreaker in the heap ensures the lexicographically smallest result among all minimum-value strings.