Problem Description

You are given a string s that contains only lowercase English letters and the character '?'. Your task is to replace all '?' characters with lowercase letters following these rules:

1. No consecutive repeating characters: After replacing all '?' characters, the resulting string should not have any two adjacent characters that are the same.

2. Cannot modify non-'?' characters: You can only change '?' characters; all other lowercase letters must remain unchanged.

3. Guaranteed solvability: The input guarantees that there are no consecutive repeating characters among the existing lowercase letters (excluding '?' characters).

The solution works by iterating through each character in the string. When a '?' is encountered, the algorithm tries to replace it with one of the letters from "abc". For each candidate letter, it checks:

• If there's a previous character (at position i-1), ensure the candidate letter is different from it
• If there's a next character (at position i+1), ensure the candidate letter is different from it

Since we only need to avoid matching the immediate neighbors, using just three letters ('a', 'b', 'c') is sufficient - at most two letters will be blocked by neighbors, leaving at least one valid choice.

For example:

• Input: "?zs" → Output: "azs" (or "bzs" or "czs")
• Input: "ubv?w" → Output: "ubvaw" (cannot use 'v' or 'w')
• Input: "j?qg??b" → Output: "jaqgacb" (each '?' is replaced to avoid consecutive repeats)

Intuition

The key insight is that we only need to worry about immediate neighbors when replacing a '?' character. Since we want to avoid consecutive repeating characters, each '?' just needs to be different from the character immediately before it and immediately after it.

Why can we use just three letters ('a', 'b', 'c')? Consider the worst-case scenario: a '?' is sandwiched between two different characters, like "a?b". In this case, we cannot use 'a' (conflicts with left neighbor) or 'b' (conflicts with right neighbor), but we can always use 'c'. Even if both neighbors were the same character, like "a?a", we'd have two available choices ('b' or 'c').

The greedy approach works perfectly here - we can process each '?' independently from left to right without worrying about future decisions. This is because:

1. Each '?' only affects its immediate neighbors
2. Once we replace a '?', it becomes a fixed character that won't change
3. Future '?' replacements will respect the already-fixed characters

The algorithm naturally handles edge cases:

• If '?' is at the beginning, we only check the right neighbor
• If '?' is at the end, we only check the left neighbor
• Multiple consecutive '?' characters are handled one by one, and each replacement creates a new constraint for the next '?'

This local decision-making strategy guarantees a valid solution because we always have at least one valid character choice out of our three options, regardless of what the neighbors are.

Solution Approach

The implementation uses a straightforward iterative approach with character replacement:

1. Convert string to list: Since strings are immutable in Python, we first convert the string s to a list of characters to allow in-place modifications.

2. Iterate through each character: We traverse the string from left to right using index i from 0 to n-1.

3. Check for '?' character: When we encounter a '?' at position i, we need to replace it with a valid lowercase letter.

4. Try candidate letters: We iterate through a small set of candidate letters "abc". For each candidate letter c:

   • Check left neighbor: If i > 0 (not the first character), verify that s[i-1] is not equal to the candidate c
   • Check right neighbor: If i+1 < n (not the last character), verify that s[i+1] is not equal to the candidate c
   • If either neighbor matches the candidate, we continue to try the next letter
   • If the candidate doesn't conflict with either neighbor, we assign s[i] = c and break out of the loop

5. Join and return: After processing all characters, we join the list back into a string and return the result.

The key algorithmic choices:

• Why only "abc"? At most two neighbors can block two letters, leaving at least one valid choice from three options
• Why left-to-right? This ensures previously replaced '?' characters are already fixed when we check them as neighbors
• Why break after finding valid character? Once we find a valid replacement, we don't need to check other options since any valid solution is acceptable

Time Complexity: O(n) where n is the length of the string (we visit each character once, and for each '?', we try at most 3 candidates)

Space Complexity: O(n) for the list conversion (required for string mutation in Python)

Example Walkthrough

Let's walk through the example "j?qg??b" step by step to see how the algorithm works:

Initial string: "j?qg??b" (converted to list: ['j','?','q','g','?','?','b'])

Step 1 - Index 0: Character is 'j', not a '?', so we skip it.

Step 2 - Index 1: Character is '?'

• Try 'a': Check left neighbor ('j') ✓ different, check right neighbor ('q') ✓ different
• Replace with 'a': ['j','a','q','g','?','?','b']

Step 3 - Index 2: Character is 'q', not a '?', so we skip it.

Step 4 - Index 3: Character is 'g', not a '?', so we skip it.

Step 5 - Index 4: Character is '?'

• Try 'a': Check left neighbor ('g') ✓ different, check right neighbor ('?') ✓ different
• Replace with 'a': ['j','a','q','g','a','?','b']

Step 6 - Index 5: Character is '?'

• Try 'a': Check left neighbor ('a') ✗ same, continue to next candidate
• Try 'b': Check left neighbor ('a') ✓ different, check right neighbor ('b') ✗ same, continue
• Try 'c': Check left neighbor ('a') ✓ different, check right neighbor ('b') ✓ different
• Replace with 'c': ['j','a','q','g','a','c','b']

Step 7 - Index 6: Character is 'b', not a '?', so we skip it.

Final result: Join the list back to string: "jaqgacb"

Notice how:

• Each '?' is processed independently
• We only need to check immediate neighbors
• The third '?' (at index 5) needed to try multiple candidates before finding 'c' that didn't conflict with either 'a' on the left or 'b' on the right
• Using just three letters ('a', 'b', 'c') was sufficient for all replacements

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string.

The algorithm iterates through each character in the string exactly once using the outer for loop. For each character that is a "?", it checks at most 3 characters ('a', 'b', 'c') in the inner loop. The inner loop performs constant time operations - checking the previous character (if exists) and the next character (if exists). Since we check at most 3 characters for each position and this is a constant, the inner loop contributes O(1) time. Therefore, the overall time complexity is O(n) * O(1) = O(n).

Space Complexity: O(n) where n is the length of the string.

The algorithm converts the input string to a list of characters with s = list(s), which creates a new list that requires O(n) space to store all the characters. The remaining variables (n, i, c) use constant space O(1). The final "".join(s) operation creates a new string, but this is part of the return value and typically not counted in auxiliary space complexity. Therefore, the overall space complexity is O(n).

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

Common Pitfalls

1. Attempting to Modify String Directly

A frequent mistake is trying to modify the string in-place without converting it to a list first:

# WRONG - This will raise TypeError: 'str' object does not support item assignment
def modifyString(self, s: str) -> str:
    for i in range(len(s)):
        if s[i] == "?":
            s[i] = 'a'  # ERROR: strings are immutable in Python

Solution: Always convert the string to a list first, modify the list, then join it back:

char_list = list(s)
# ... modifications ...
return "".join(char_list)

2. Not Checking Both Neighbors Before Replacement

Some implementations check neighbors sequentially rather than together, leading to incorrect replacements:

# WRONG - Replaces without checking if it conflicts with the right neighbor
def modifyString(self, s: str) -> str:
    char_list = list(s)
    for i in range(len(char_list)):
        if char_list[i] == "?":
            if i > 0 and char_list[i-1] == 'a':
                char_list[i] = 'b'
            else:
                char_list[i] = 'a'  # Might conflict with char_list[i+1]

Solution: Check both neighbors before deciding on a replacement character, using a loop to try different options.

3. Using Insufficient Candidate Characters

Trying to use only two candidate characters (like 'a' and 'b') can lead to impossible situations:

# WRONG - Only using 'a' and 'b' can fail for input like "a?b"
for replacement_char in "ab":  # Not enough options
    # Both 'a' and 'b' would be blocked by neighbors

Solution: Use at least three candidate characters. Since a position can have at most two neighbors, three options guarantee at least one valid choice.

4. Incorrect Boundary Checking

Failing to properly check array boundaries can cause IndexError:

# WRONG - Always checks both neighbors without boundary validation
if char_list[i-1] == replacement_char or char_list[i+1] == replacement_char:
    continue  # IndexError when i=0 or i=n-1

Solution: Always validate indices before accessing array elements:

has_left_conflict = (i > 0 and char_list[i - 1] == replacement_char)
has_right_conflict = (i + 1 < n and char_list[i + 1] == replacement_char)

5. Forgetting to Break After Finding Valid Replacement

Continuing to iterate through candidates after finding a valid one wastes computation and might lead to logical errors in more complex variations:

# INEFFICIENT - Continues checking even after finding valid replacement
for replacement_char in "abc":
    if not has_conflict:
        char_list[i] = replacement_char
        # Missing break - will keep iterating unnecessarily

Solution: Add a break statement immediately after assigning the valid character to exit the inner loop early.