Replace All ?'s to Avoid Consecutive Repeating Characters — LeetCode 1576 Python Solution

The problem

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.

Example

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".

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems