Code Implementation

class Solution:
    def modifyString(self, s: str) -> str:
        s = list(s)
        for i in range(len(s)):
            if s[i] == '?':
                for c in "abc":
                    if (i > 0 and s[i-1] == c) or (i+1 < len(s) and s[i+1] == c):
                        continue
                    s[i] = c
                    break
        return "".join(s)
      

class Solution {
public:
    string modifyString(string s) {
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '?') {
                for (char c = 'a'; c <= 'c'; ++c) {
                    if ((i > 0 && s[i-1] == c) || (i+1 < s.size() && s[i+1] == c))
                        continue;
                    s[i] = c;
                    break;
                }
            }
        }
        return s;
    }
};
      

class Solution {
    public String modifyString(String s) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '?') {
                for (char c = 'a'; c <= 'c'; c++) {
                    if ((i > 0 && arr[i-1] == c) || (i+1 < arr.length && arr[i+1] == c))
                        continue;
                    arr[i] = c;
                    break;
                }
            }
        }
        return new String(arr);
    }
}
      

var modifyString = function(s) {
    let arr = s.split('');
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '?') {
            for (let c of ['a', 'b', 'c']) {
                if ((i > 0 && arr[i-1] === c) || (i+1 < arr.length && arr[i+1] === c))
                    continue;
                arr[i] = c;
                break;
            }
        }
    }
    return arr.join('');
};
      

Problem Description

Given a string s consisting of lowercase English letters and the character '?', your task is to replace every '?' in s with a lowercase English letter so that no two consecutive characters are the same. Return any valid string after all replacements.

• You must replace every '?' in the string.
• It is guaranteed that at least one valid answer exists.
• Adjacent characters must not be the same after replacement.
• You can use any lowercase letter for each '?'.

Thought Process

At first glance, the brute-force approach would be to try every possible letter for every '?' and check if the resulting string has consecutive repeating characters. However, this is inefficient because the number of combinations grows exponentially with the number of '?' characters.

The optimization comes from realizing that for each '?', we only need to ensure that the replacement character is different from its immediate neighbors (the previous and next characters). Since there are 26 letters, and at most two neighbors, we can always pick a letter that is not equal to either neighbor. We do not need to consider the entire string's context, only the local context of each '?'.

Solution Approach

Let's break down the solution step by step:

1. Convert the string to a mutable sequence (like an array or list), since strings are immutable in some languages.
2. Iterate through each character in the sequence.
3. Whenever a '?' is encountered:
   • Try each candidate letter (typically 'a', 'b', or 'c' is sufficient, as only two neighbors need to be avoided).
   • Check if the candidate is different from the previous character (if any) and the next character (if any).
   • As soon as a valid letter is found, replace the '?' with it and move to the next character.
4. After processing all characters, join the sequence back into a string and return it.

This approach is efficient because:

• It only checks the immediate neighbors for each '?'.
• It processes the string in a single pass (O(n) time).
• No extra data structures are needed beyond the mutable sequence.

Example Walkthrough

Let's consider the input s = "a?b??a".

1. Start with ['a', '?', 'b', '?', '?', 'a'].
2. At index 1: '?'
   • Neighbors: previous is 'a', next is 'b'.
   • Try 'a' (same as previous) - skip.
   • Try 'b' (same as next) - skip.
   • Try 'c' - valid! Replace with 'c'.
   • Now the string is ['a', 'c', 'b', '?', '?', 'a'].
3. At index 3: '?'
   • Neighbors: previous is 'b', next is '?'.
   • Try 'a' (not 'b') - valid! Replace with 'a'.
   • Now the string is ['a', 'c', 'b', 'a', '?', 'a'].
4. At index 4: '?'
   • Neighbors: previous is 'a', next is 'a'.
   • Try 'a' (same as neighbors) - skip.
   • Try 'b' - valid! Replace with 'b'.
   • Now the string is ['a', 'c', 'b', 'a', 'b', 'a'].
5. Final string: "acbaba", which has no consecutive repeating characters.

Time and Space Complexity

• Brute-force approach: For each '?', try all 26 possible replacements, and for each combination, check the entire string for consecutive repeats. If there are k question marks, this is O(26^k \cdot n), which is infeasible for large k.
• Optimized approach: We process each character once, and for each '?' we try at most three candidates ('a', 'b', 'c'). Thus, the time complexity is O(n), where n is the length of the string.
• Space complexity: We use O(n) extra space if we convert the string to a mutable array, otherwise O(1) if in-place mutation is possible.

Summary

The key insight in this problem is that each '?' only needs to differ from its immediate neighbors, so we can greedily pick a valid letter for each one. This local decision ensures the global constraint (no consecutive repeats) is satisfied, and the use of just three letters guarantees a solution exists. The algorithm is efficient, simple, and easy to implement in any language.