小欧的red填充

OPPO 笔试真题 · 2023 秋招 · 研发岗

判题请到牛客原题提交。

题目描述

给定一个字符串，仅由'r'、'e'、'd'和'?'四种字符组成。你需要把所有的'?'字符变成'r'、'e'、'd'三种字符中的任意一种，使得任意长度为3的连续子串中，'r'、'e'、'd'三种字母的出现次数相同。你能帮帮她吗？

共有$q$次询问。

输入格式

第一行输入一个正整数$q$，代表询问次数。

接下来的$q$行，每行输入一个仅由'r'、'e'、'd'和'?'四种字符组成的字符串，代表一次询问。

所有的字符串总长度不超过200000。

输出格式

输出$q$行，每行代表一次询问的答案。

如果可以完成修改，请输出一个合法的字符串。有多解时输出任意即可。

否则输出一个字符串"No"。

示例

示例 1

输入：

3
e???d??
r??e
??

输出：

edredre
No
rd

---

解题思路

第一步：把「每个窗口都平衡」翻译成结构条件

长度 3 的窗口里 r、e、d 出现次数相同，而窗口一共只有 3 个位置，
所以每个窗口必须恰好是 r、e、d 各一个 —— 也就是 red 的一个排列。

第二步：相邻两个窗口共享两个字符，推出周期为 3

考虑相邻的两个窗口 $s[i..i+2]$ 和 $s[i+1..i+3]$。它们都必须各含一个 r、e、d，
而 $s[i+1]$、$s[i+2]$ 是两个窗口共有的，这两格已经用掉了 r/e/d 里的两种，
剩下那个字符必然同时等于 $s[i]$ 和 $s[i+3]$。因此

$$s[i] = s[i+3] \quad \text{对任意合法的 } i \text{ 成立}$$

也就是说，整串以 3 为周期：位置 $0, 3, 6, \dots$ 上的字符全都一样，
位置 $1, 4, 7, \dots$ 一样，位置 $2, 5, 8, \dots$ 一样。

第三步：周期只有 6 种可能

既然整串由前三个字符决定，而前三个字符构成第一个窗口、必须两两不同，
那么答案只可能是下面 6 个模板的无限重复：

red   rde   erd   edr   dre   der

于是每个询问只要依次试这 6 个模板：

• 逐个位置比对，遇到既不是 ? 又不等于模板字符的位置，这个模板作废；
• 第一个通过比对的模板就是答案，? 按模板填上；
• 6 个模板全部作废，说明没有任何合法填法，输出 No。

若串长不足 3，则不存在长度为 3 的子串，条件天然满足，? 随便填（代码里填 r）。

---

完整代码实现

import sys

# 三个字符的全部排列；每个模板无限重复就是一棵合法答案
PERMS = ("red", "rde", "erd", "edr", "dre", "der")


def fill(s: str):
    """按周期 3 填充，返回任意一个合法串；无解返回 None"""
    # 长度不足 3 时没有任何窗口，'?' 填什么都合法
    if len(s) < 3:
        return s.replace('?', 'r')
    for p in PERMS:
        ok = True
        for i, ch in enumerate(s):
            if ch != '?' and ch != p[i % 3]:
                ok = False
                break
        if ok:
            return ''.join(p[i % 3] for i in range(len(s)))
    return None


def solve() -> None:
    """逐个询问套 6 个周期模板"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    q = int(data[0])

    out = []
    for k in range(q):
        s = data[1 + k].decode()
        ans = fill(s)
        out.append(ans if ans is not None else "No")

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

询问 1：s = "e???d??"

位置	0	1	2	3	4	5	6
字符	e	?	?	?	d	?	?

• 位置 0 是 e，模板的第一位必须是 e，候选缩小到 erd、edr；
• 位置 4 是 d，而 $4 \bmod 3 = 1$，模板的第二位必须是 d，只剩 edr；
• 用 edr 反复填：e d r | e d r | e。

输出 edredre，与题面示例一致。检查三个窗口：edr、dre、red、edr、dre，每个都是三个字符各一个。

询问 2：s = "r??e"

位置 0 是 r、位置 3 是 e，但周期要求 $s[3] = s[0]$，即 e 必须等于 r，矛盾。
对照 6 个模板，位置 3 对应的都是模板的第一位，而被固定成 e，与 r 冲突 —— 全部作废。

输出 No。

询问 3：s = "??"

长度 2，没有长度为 3 的子串，条件恒成立，把两个 ? 都填成 r 即可。

输出 rr（题面示例给的是 rd，任意合法答案都算对）。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
逐窗口检查合法性再回溯填 ?	指数级	O(n)	需要搜索，没必要
枚举 6 个周期模板	O(6 · L) = O(L)	O(L)	推荐，L 为串长，总长不超过 2e5

---

易错点总结

1. 只试 red 一种周期

合法的周期有 6 种（r/e/d 的任意排列）。只试 red 会漏掉大量有解的询问，
比如 e???d?? 的正解就是以 e 开头的 edr。

2. 长度小于 3 时错误地输出 No

rr 这样的串没有任何长度为 3 的子串，条件是空真，它本身就是合法答案。
代码里对 len(s) < 3 单独处理。

3. 想改动已有字符

题目只允许替换 ?。已有字符与模板冲突时，这个模板直接作废，不能「改一改凑上去」。

4. 输出行数不对

有 $q$ 个询问就要输出 $q$ 行。用列表收集结果再一次性 join 输出，
不要在处理过程中提前 return。

5. No 的拼写

题面要求输出的是 No（大写 N、小写 o），不是 NO 也不是 no。

6. 以为要检查「每个字符出现次数相等」这一全局条件

真正的约束只在每个长度为 3 的窗口上；一旦满足窗口条件，周期结构自动让全局也平衡，
不需要额外校验。

---

扩展思考

• 推广到长度 k 的窗口、k 个字符的字母表：同样的推导给出 $s[i] = s[i+k]$，
  答案就是 $k!$ 个模板里能对上的那些，复杂度 $O(k! \cdot L)$。
• 如果要求「任意长度不少于 3 的子串都平衡」：条件会强得多，只有周期为 3
  且每个周期块恰好是排列的串才满足，结论不变但推导更绕。
• 如果允许每个 ? 有代价（比如变成 e 要花 2 块钱）：就变成「在 6 个模板里挑总代价最小的」，
  一次线性扫描即可，是本题的自然加强版。
• 这类「相邻窗口共享元素 → 推出周期性」的技巧，在字符串周期、循环节、滑动窗口类题目里反复出现。

---

相关题目

• 小欧的字符串构造
• 小欧的字符串判定