Replace All ?'s to Avoid Consecutive Repeating Characters

LeetCode Replace All ?'s to Avoid Consecutive Repeating Characters (Problem 1576) asks you to replace every '?' character in a string so that no two adjacent characters are the same.

The problem

You are given a string s containing only lowercase English letters and '?' characters. Replace every '?' with any lowercase letter so that the resulting string has no two adjacent characters that are equal.

You can choose any valid replacement. It is guaranteed that a solution always exists.

Examples:

• s = "?zs" returns "azs" (the '?' at index 0 becomes 'a', which does not match 'z' to its right)
• s = "ubv?w" returns "ubvaw" (the '?' at index 3 becomes 'a', which differs from both 'v' and 'w')
• s = "j?qg??b" returns "jaqgacb" (each '?' gets a letter that avoids clashing with its neighbors)

The approach

The key insight is that you only need three letters to guarantee a valid choice. At any position, there are at most two neighbors (one on the left, one on the right). With three candidates, 'a', 'b', and 'c', at least one of them will differ from both neighbors.

The algorithm is a single left-to-right scan:

1. Convert the string to a mutable list of characters.
2. For each index i, if s[i] is '?', check the left neighbor (s[i-1] if it exists) and the right neighbor (s[i+1] if it exists).
3. Pick the first character from 'a', 'b', 'c' that does not match either neighbor.
4. Replace the '?' with that character and move on.

By the time you reach a '?', any earlier '?' to its left has already been replaced. So s[i-1] is always a concrete letter, not another '?'. The right neighbor might still be '?', but that is fine. You only need to avoid matching it, and '?' is not a lowercase letter, so it will never equal 'a', 'b', or 'c'.

Step-by-step walkthrough

Here is the algorithm running on "j?qg??b". Watch how each '?' gets replaced as the scan moves left to right.

Notice that when the scan reaches index 5, the left neighbor (index 4) has already been resolved to 'a'. The right neighbor (index 6) is 'b'. So the algorithm picks 'c', the first candidate that avoids both.

The code

def modify_string(s: str) -> str:
    chars = list(s)
    n = len(chars)
    for i in range(n):
        if chars[i] == "?":
            left = chars[i - 1] if i > 0 else ""
            right = chars[i + 1] if i < n - 1 else ""
            for c in "abc":
                if c != left and c != right:
                    chars[i] = c
                    break
    return "".join(chars)

Here is what each part does:

• Convert to list. Python strings are immutable, so you work with a list of characters instead.
• Scan left to right. For each index i, check if chars[i] is '?'.
• Check neighbors. Grab the left and right neighbors. If the index is out of bounds, use an empty string (which will never match any candidate).
• Pick a candidate. Loop through 'a', 'b', 'c'. The first one that differs from both neighbors wins.
• Join and return. Convert the list back to a string.

Complexity analysis

Time: O(n) where n is the length of the string. You visit each character exactly once. The inner loop over 'a', 'b', 'c' runs at most 3 iterations per '?', which is constant.

Space: O(n) for the character list. If the language allows in-place mutation (like C++ or Java with a char array), you can do this in O(1) extra space.

The building blocks

Greedy left-to-right scan

The idea of processing elements one at a time from left to right, making a locally optimal choice at each step, is the greedy pattern. Here, the "locally optimal" choice is any letter that avoids matching neighbors. There is no need for backtracking because three candidates always suffice for two constraints.

This same scan-and-decide approach appears in problems like gas station (greedy circular scan), jump game (greedy reach), and candy distribution (greedy pass).

Neighbor-aware replacement

Checking the left and right neighbors before choosing a value is a common string and array technique. You will see it in problems that involve adjacent constraints, such as wiggle sort (each element must alternate between greater and less than its neighbors) and painting houses (no two adjacent houses share a color).

Edge cases

All question marks. A string like "????" works fine. The first '?' picks 'a' (no left neighbor, right is '?'). The second picks 'b' (left is 'a', right is '?'). The pattern alternates: "abab...".

No question marks. If the string has no '?' characters, the loop skips every index and returns the original string unchanged.

Single character. The string "?" becomes "a". There are no neighbors, so the first candidate always works.

Question mark at the edges. When '?' appears at index 0 or the last index, there is only one neighbor to avoid. The algorithm handles this naturally because the missing neighbor defaults to an empty string.

Adjacent question marks. Two or more '?' characters in a row are fine. Each one is resolved in order, and by the time you reach the next '?', its left neighbor is already a concrete letter.

From understanding to recall

This problem is easy to understand: scan left to right, pick a letter that avoids matching neighbors. But will you remember the trick of using just three candidates ('a', 'b', 'c') when you see a similar constraint problem in an interview? Will the neighbor-checking pattern come to you automatically?

Spaced repetition helps lock in the building blocks. Instead of re-reading this solution, you drill the greedy scan pattern and the neighbor-aware replacement technique at increasing intervals. After a few reps spread across days, the pieces become automatic. When a problem says "fill in blanks subject to adjacent constraints," you already know the shape of the solution.

Related posts

• Longest Substring Without Repeating Characters - Another string problem where you track characters to avoid duplicates, using a sliding window instead of a greedy scan
• Valid Anagram - An easy string problem that builds the frequency counter pattern, a core building block for string manipulation
• Find the Index of the First Occurrence in a String - A string scanning problem where you process characters left to right looking for a match