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.

#1576

Easy

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

替换所有的问号

给你一个仅包含小写英文字母和 '?' 字符的字符串 s ，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何连续重复的字符。注意：你不能修改非 '?' 字符。题目测试用例保证除 '?' 字符之外，不存在连续重复的字符。在完成所有转换（可能无需转换）后返回最终的字符…

字符串

题目描述

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你不能修改非 '?' 字符。

题目测试用例保证除 '?' 字符之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符

lightbulb

解题思路

方法一：模拟

我们遍历字符串，对于每个位置，如果该位置是 ?，则枚举字符 'a'、'b'、'c'，如果该字符 $c$ 与前后字符都不相同，则将该位置替换为该字符，否则继续枚举下一个字符。

遍历结束后，返回字符串即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1578 使绳子变成彩色的最短时间 #1573 分割字符串的方案数 #1585 检查字符串是否可以通过排序子字符串得到另一个字符串