Replace All ?'s to Avoid Consecutive Repeating Characters

Replace All ?'s to Avoid Consecutive Repeating Characters

What is this problem about?

The Replace All ?'s to Avoid Consecutive Repeating Characters interview question gives you a string containing lowercase letters and '?' wildcards. You must replace each '?' with a lowercase letter such that no two adjacent characters in the resulting string are the same. Any valid replacement is acceptable — you just need to ensure no consecutive duplicates remain after all wildcards are filled.

Why is this asked in interviews?

Microsoft asks this problem to evaluate greedy character assignment under local constraints. It tests a candidate's ability to handle placeholder replacement while considering both left and right neighbors simultaneously. It is a practical exercise in constraint satisfaction, which applies to template filling, code generation, and string sanitization problems in real software systems.

Algorithmic pattern used

The pattern is greedy character substitution with a small candidate set. For each '?' in the string, try characters 'a', 'b', 'c' in order. Pick the first one that differs from both the left neighbor (index i-1) and the right neighbor (index i+1). Since you only need to avoid two specific characters, at most three candidates are needed — one of 'a', 'b', 'c' is always safe by the pigeonhole principle.

Example explanation

Input: "?zz?"

• Index 0 ('?'): left=none, right='z'. Try 'a': not 'z' → place 'a'.
• Index 3 ('?'): left='z', right=none. Try 'a': not 'z' → place 'a'. Result: "azza".

Input: "ab?ac":

• Index 2 ('?'): left='b', right='a'. Try 'a': equals right neighbor. Try 'b': equals left neighbor. Try 'c': works! Result: "abcac".

Common mistakes candidates make

• Checking only the left neighbor and ignoring the right, causing adjacent duplicates on the right side.
• Trying more than three characters when three always suffice.
• Forgetting to convert the string to a mutable structure (like a list) before modifying it in languages with immutable strings.
• Changing non-'?' characters, which must remain unchanged.

Interview preparation tip

For the Replace All ?'s to Avoid Consecutive Repeating Characters coding problem, the string interview pattern is about local constraint satisfaction with minimal candidates. Prove why three letters suffice: at most two neighbors to avoid, three choices guarantee one is always valid. Microsoft interviewers appreciate when you articulate this reasoning before coding — it shows structured thinking over trial and error.