Replace All ?'s to Avoid Consecutive Repeating Characters - Video Solutions

Problem Overview: You receive a string containing lowercase letters and the character ?. Each ? must be replaced with a lowercase letter so that no two adjacent characters are the same. The final string must preserve the existing characters while ensuring every neighbor pair differs.

Approach 1: Left to Right Replacement (O(n) time, O(1) space)

Scan the string from left to right and immediately resolve every ?. For each position, try a small set of candidate letters (typically 'a', 'b', 'c') and choose one that differs from both the previous character and the next character if it already exists. Because only adjacent conflicts matter, checking two neighbors is enough. This greedy strategy works since the alphabet gives enough choices to avoid collisions while keeping the replacement local.

Implementation converts the string to a mutable array, iterates once, and performs constant-time neighbor checks for every ?. The approach runs in O(n) time with O(1) extra space since only a few temporary characters are tested. This pattern appears frequently in string manipulation problems where constraints depend only on adjacent elements.

Approach 2: Two-pointer Method (O(n) time, O(1) space)

The two-pointer variant handles segments of consecutive ?. One pointer marks the start of a block of unknown characters while another scans forward until the block ends. After identifying the segment, fill characters sequentially while ensuring the first replacement differs from the left boundary and the last replacement differs from the right boundary.

Inside the segment, alternate safe characters so no internal duplicates appear. This method explicitly treats ??? sequences as small subproblems and resolves them while respecting boundary characters. Time complexity remains O(n) because each index is processed once, and the algorithm uses O(1) space.

Problems like this highlight greedy reasoning in string processing and often appear alongside patterns from two pointers or simple greedy decisions where only local constraints matter.

Recommended for interviews: The left-to-right greedy replacement is the expected solution. It is simpler, runs in linear time, and demonstrates that you recognized only adjacent comparisons matter. Mentioning the segment-based or two-pointer variation shows deeper reasoning, but the single-pass greedy implementation is usually what interviewers expect.