#1576

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Replace All ?'s to Avoid Consecutive Repeating Characters

Solve LeetCode 1576 by scanning left to right and replacing each ? with a letter different from its neighbors.

Problem Statement

You are given a string made of lowercase letters and ? characters. Your job is to replace every ? with a lowercase letter while keeping all existing letters unchanged, and the finished string must have no two adjacent characters that are the same.

The input already avoids adjacent duplicates among the non-? letters, so the only risk comes from how each ? is filled. For example, in s = "?zs", choosing "a" gives "azs", which is valid, while choosing "z" creates "zzs", which breaks the rule. Any valid completed string can be returned.

Examples

Example 1

Input: s = "?zs"

Output: "azs"

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"

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 consist of lowercase English letters and '?'.

Solution Approach

Turn the string into a mutable array

Strings are easier to solve here if you copy the characters into an array and edit in place. That lets you process one position at a time and immediately use each replacement when deciding the next ?. This matters on runs like "???", where the choice at index i affects index i + 1.

Greedy left-to-right replacement

Walk from left to right. If the current character is not ?, leave it alone. If it is ?, inspect the left neighbor from the already-built array and the right neighbor from the original remaining characters, then pick the first letter from "a" to "z" that matches neither side. Since a position must avoid at most two letters, this local choice is always enough.

Why local decisions are safe

This problem does not need backtracking because each replacement only interacts with adjacent positions. Once you choose a character different from the left and right neighbors, that index is permanently safe. The guarantee that the original non-? characters do not already contain consecutive repeats prevents hidden conflicts from appearing later.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With the standard greedy scan, the algorithm visits each character once and tries at most 26 letters for each ?, so the time complexity is O(n) with a small constant factor. Using a character array for in-place updates gives O(n) space if you count the output buffer, or O(1) extra working space beyond the returned string.

What Interviewers Usually Probe

They want you to notice that each ? only depends on its immediate left and right neighbors, not the whole string.
They are checking whether you can justify why greedy works without backtracking on adjacent-character constraints.
They expect careful handling of edge indices and consecutive ? blocks like "a??b" or "???".

Common Pitfalls or Variants

Common pitfalls

Reading the right neighbor after you already overwrote it incorrectly, especially when mutating the string in place.
Choosing a replacement that avoids the left side but forgets to check the next fixed character, which can create a duplicate immediately.
Overengineering the problem with recursion or full search even though each ? only needs to dodge at most two letters.

Follow-up variants

Return the lexicographically smallest valid string instead of any valid string by always picking the smallest allowed letter.
Extend the rule so no character can match within distance two, which changes the local check from two neighbors to four nearby positions.
Restrict replacements to a smaller alphabet such as {a, b, c}, which still works here because avoiding two adjacent letters only needs three choices.

FAQ

What is the main pattern in Replace All ?'s to Avoid Consecutive Repeating Characters?

The core pattern is a greedy string scan. At each ?, you only need a character different from the left neighbor and the right neighbor, so a local choice is enough to finish the whole string correctly.

Why does checking only adjacent characters work in this problem?

The constraint is only about consecutive repeating characters, so each index is affected only by positions directly beside it. Once a replacement differs from both neighbors, that position cannot create any future violation.

Do I need to try all 26 letters for every ?

In practice you can stop as soon as you find the first valid letter. The loop may consider up to 26 letters, but because only two letters are blocked by neighbors, a valid pick appears quickly.

How do consecutive ? characters get handled correctly?

Processing left to right solves that cleanly. After you replace the first ?, it becomes the fixed left neighbor for the next ?, while the untouched next character still serves as the right-side check when needed.

Can this problem be solved with only three candidate letters?

Yes. Because a ? only needs to avoid matching at most two adjacent characters, three distinct letters are sufficient to guarantee a valid choice. Many implementations still iterate over "a" to "z" for simplicity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

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)

Continue Practicing

#1578 minimum time to make rope colorful #1573 number of ways to split a string #1585 check if string is transformable with substring sort operations