Replace All ?'s to Avoid Consecutive Repeating Characters

Difficulty: Easy | Acceptance: 45.30% | Paid: No Topics: String

Given a string s containing only lowercase English letters and the ’?’ character, convert all the ’?’ characters into lowercase letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non-’?’ characters.

Please return the final string if there is a way to replace all ’?’ characters. If there is no way to replace all ’?’ characters, return an empty string "".

Examples

Example 1

Input:

s = "?zs"

Output:

"azs"

Explanation: There are 25 solutions for this problem. From “azs” to “yzs”, all are valid. Only “z” is an invalid modification as the string will consist of consecutive repeating characters in “zzs”.

Example 2

Input:

s = "ubv?w"

Output:

"ubvaw"

Explanation: There are 24 solutions for this problem. Only “v” and “w” are invalid modifications as the strings will consist of consecutive repeating characters in “ubvvw” and “ubvww”.

Constraints

1 <= s.length <= 100
s consists of lowercase English letters and '?'.

• Greedy Iteration
• Randomized Replacement

Examples

Example 1

Input: s = "?zs"
Output: "azs"

Example 2

Input: s = "ubv?w"
Output: "ubvaw"

Example 3

Input: s = "j?qg??b"
Output: "jaqgacb"

Constraints

1 <= s.length <= 100
s consist of lowercase English letters and '?'.

Greedy Iteration

Intuition We iterate through the string character by character. Whenever we encounter a ’?’, we simply try to replace it with a character (e.g., ‘a’, ‘b’, or ‘c’) that is different from both the previous character and the next character. Since the alphabet has 26 letters and we only need to avoid at most 2 specific characters, a valid replacement always exists.

Steps

• Convert the string into a mutable data structure (like a character array or list).
• Iterate through the indices of the string.
• If the current character is ’?’, loop through potential replacement characters (‘a’, ‘b’, ‘c’).
• Check if the potential character is different from the left neighbor (if it exists) and the right neighbor (if it exists).
• Assign the first valid character found to the current position.
• After processing all characters, join the array/list back into a string and return it.

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

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once, and for each ’?’ we perform a constant amount of work (checking at most 3 characters).
• Space: O(n) to store the character array/list. In languages where strings are mutable (like C++), this could be O(1) extra space, but generally O(n) is used for the conversion.
• Notes: This is the most optimal deterministic approach.

Randomized Replacement

Intuition Since the problem asks for any valid string and the alphabet size (26) is significantly larger than the number of constraints (2 neighbors), we can use a randomized approach. We repeatedly fill the ’?’ characters with random letters and check if the resulting string is valid. The probability of a random collision is low, so this usually converges quickly.

Steps

• Convert the string to a mutable array.
• Loop indefinitely until a valid string is found.
• Iterate through the array. If a character is ’?’, replace it with a random lowercase letter.
• After filling all ’?’, check if the string contains any consecutive repeating characters.
• If valid, return the string. If not, repeat the process.

import random

class Solution:
    def modifyString(self, s: str) -> str:
        while True:
            res = list(s)
            for i in range(len(res)):
                if res[i] == '?':
                    res[i] = chr(random.randint(97, 122))
            valid = True
            for i in range(len(res) - 1):
                if res[i] == res[i+1]:
                    valid = False
                    break
            if valid:
                return ''.join(res)

Complexity

• Time: O(k * n), where n is the length of the string and k is the number of attempts. In the worst case, k could be very large, but given the probability of collision is (1/26) per pair, k is expected to be very small (constant).
• Space: O(n) for the character array.
• Notes: While expected time is fast, it is non-deterministic. The Greedy approach is preferred for guaranteed performance.