更新题目 424. Longest Repeating Character Replacement

题目 lc424 · 修改（rev 4） · cc · 2026-10-26 00:04
body

@@ -1,51 +1,83 @@
 ## 题目
 
-给一个只含大写字母的字符串和整数 k，最多可以把 k 个字符改成任意大写字母，求修改后由同一个字母组成的最长子串的长度。
+给一个只含大写字母的字符串 `s` 和整数 `k`，最多可以把 `k` 个字符改成任意大写字母，求修改后由同一个字母组成的最长子串的长度。
 
 [LeetCode 原题](https://leetcode.com/problems/longest-repeating-character-replacement/)
 
+LeetCode 上的范围是 `1 <= len(s) <= 10^5`、`0 <= k <= len(s)`。签名写成 `character_replacement(s: str, k: int) -> int`。
+
+例子：`s = "AABABBA"`、`k = 1`，答案是 4。长度 4 的子串里有两个改一次就行：`AABA`（下标 0 到 3，把下标 2 的 `B` 改成 `A`）和 `BABB`（下标 2 到 5，把下标 3 的 `A` 改成 `B`）。长度 5 的子串里最多的字母只有 3 个，要改 2 次，超过 k。
+
 ## 面经里怎么考的
 
-Temu 的 Senior SWE 二面（2026-08，PracHub 转载）考的是变体：**返回最长子串有几个**，不是长度（写法见下面 Follow-up）。楼主一开始没想到滑动窗口，面试官提示后才写出来；之后面试官说有 bug，楼主找了好几分钟，解释清楚后面试官才认可其实没 bug。教训：先把「窗口合法 ⇔ 窗口长度 − 窗口里最多的字母次数 ≤ k」讲清楚再写，被说有 bug 时拿一个小例子当场走一遍。
+Temu 的 Senior SWE 二面（2026-08，PracHub 转载）考的是变体，要返回最长子串有几个，长度不用返回（写法见下面 Follow-up）。楼主一开始没想到滑动窗口，面试官提示后才写出来。之后面试官说有 bug，楼主找了好几分钟，解释清楚后面试官才认可其实没 bug。从这次能学到两件事。写代码前先把「窗口合法 ⇔ 窗口长度 − 窗口里最多的字母次数 ≤ k」讲清楚。被说有 bug 时，拿一个小例子当场走一遍，比如「思路」里的 `AAB`。
+
+Temu Order 组 2026-10-21 的「第二轮技术电面」考的是进阶版，要求输出所有的替换组合。楼主说题面是中文、样例不够，输入输出要自己问清楚，这一轮楼主挂了。现在的资料里没有这道进阶题的确切题面，「Follow-up」里列了要问的问题和一种【推断】的理解。
 
 ## 思路
 
-一个窗口能否通过 k 次修改变成全是同一个字母，取决于「窗口长度减去窗口里出现最多的那个字母的次数」，这就是需要改掉的字符个数，不超过 k 就合法。窗口变长时这个值只增不减，满足单调性，可以套可变长窗口模板。巧妙的地方是 `maxCount`（历史上窗口内出现最多的字母次数）在收缩时不需要减小：答案要变得更长，必须出现一个比历史 `maxCount` 更大的计数，而 `maxCount` 偏大时，窗口只会整体向右平移、长度不变，不会让答案变错。
+一个窗口能不能通过最多 k 次修改变成同一个字母，看「窗口长度减去窗口里出现最多的那个字母的次数」。最省的改法是把其余字母全改成出现最多的那个，这个差就是要改的字符个数，不超过 k 就合法。窗口往外扩时这个差只增不减，往里缩时只减不增，所以可以套可变长滑动窗口：右端每次进一格，差超过 k 就把左端往右收。
 
-## 步骤
+> [!say] A window is valid if its length minus the count of its most frequent letter is at most k, because that difference is exactly how many characters I need to replace.
 
-1. 建长度为 26 的计数数组 `cnt`，令 `left = 0`、`maxCount = 0`。
-2. 遍历 `right`，把 `s[right]` 的计数加 1，并更新 `maxCount = max(maxCount, cnt[s[right]])`。
-3. 当 `right - left + 1 - maxCount > k` 时，把 `s[left]` 的计数减 1，`left` 加 1。
-4. 收缩结束后，用 `right - left + 1` 更新答案。
+这道题的关键一步是窗口里的最大计数 `maxf`（很多题解叫 `maxCount`）。它在右端加字母时更新为 `max(maxf, 新字母的计数)`，收缩时不回退。这一行看起来像 bug，面试时要能讲清它为什么对。`maxf` 是历史上任何时刻窗口里出现过的最大计数，所以它总是大于等于当前窗口里每个字母的真实次数，只会偏大，不会偏小。下面分两步说明，它偏大既不会漏掉答案，也不会把答案算大。
 
-## 易错点
+第一步，不会漏掉最长的合法窗口。设最长的合法窗口是下标 i 到 j，目标字母是 c，窗口里不是 c 的字符不超过 k 个。假设右端走到 j 的过程中（含 j 那一步），左端越过了 i，也就是在 `left == i`、右端为某个 r（r ≤ j）时触发了收缩。这时窗口 i 到 r 是 i 到 j 的一段，不是 c 的字符也不超过 k 个，所以「长度 − c 的真实次数 ≤ k」。`maxf` 不小于 c 的真实次数，「长度 − `maxf`」只会更小，收缩条件不成立，矛盾。所以右端到 j 时左端还没过 i，窗口至少和最长合法窗口一样长。
 
-- 收缩条件里窗口长度写成 `right - left`，差一，相当于多允许了一次修改。
-- 收缩时试图把 `maxCount` 减 1 是错的，因为被移出的字母不一定是出现最多的那个。要么像上面一样保留旧值并能讲清为什么正确，要么每次重新扫描 26 个计数。
-- 这题因为 `maxCount` 不减小，每次最多只需要收缩一格，所以很多题解写的是 `if`。把这个 `if` 照抄到 340、904 这类题里就会出错，养成写 `while` 的习惯更安全。
+第二步，答案不会被算大，要两个观察。
 
-## 复杂度
+- 窗口长度只增不减。上一步结束时「长度 − `maxf`」≤ k。加一个字母后长度多 1，`maxf` 不会变小，差最多超出 1，左端收一格就回到 ≤ k，所以每一步最多收一格。
+- 窗口变长的那一步，窗口是合法的。一种情况是这一步 `maxf` 变大了，新值就是刚加进来那个字母在当前窗口里的真实次数，`maxf` 是准的，窗口合法。另一种情况是 `maxf` 没变。`maxf` 变大的那一步不会收缩（长度加 1，`maxf` 也加 1，差不变），而收缩之后长度正好等于 `maxf + k`，之后 `maxf` 不变时每加一个字母都要再收一格，长度不会再涨。所以这种情况下 `maxf` 上次更新以后左端没动过，当前窗口包含 `maxf` 上次更新时的那个窗口，那个字母至少还有 `maxf` 个，`maxf` 仍然是准的，窗口合法。
 
-时间 O(n)，每一步只做 O(1) 的更新；空间 O(1)，计数数组固定 26 位。
+两个观察合起来，`best` 每次变大都对应一个真实的合法窗口。`maxf` 偏大的代价只是窗口在某些步骤不合法，但这些步骤里窗口只平移，长度不涨，不影响 `best`。
 
-## Follow-up
+拿 `s = "AAB"`、`k = 0` 走一遍（2026-10-26 跑过，打出了每一步的窗口）。right = 1 时窗口是 `AA`，`maxf = 2`，`best = 2`。right = 2 加进 `B`，`3 − 2 = 1 > 0`，左端收一格，窗口变成 `AB`。`maxf` 还是 2，按它算 `2 − 2 = 0`，不再收缩。窗口 `AB` 其实要改一次，不合法，但长度 2 没有超过 `best`，答案仍是 2。
 
-**Temu 考过的变体：最长的合法子串有几个。** 先用原题求出最长长度 `L`，再用固定长度 `L` 的窗口扫一遍，数满足 `L - 窗口内最多字母次数 <= k` 的窗口。先和面试官对齐「个数」按起点不同算还是按内容去重；去重就把合法窗口的子串放进 set。
+> [!say] I never decrease maxCount when the window shrinks. A stale maxCount is only ever too large, so it makes me shrink less, and I can't miss the longest valid window. The window may be invalid for a few steps, but during those steps it only slides. Whenever it gets longer, maxCount is a real count in the current window, so that window is valid.
+
+不想在面试里讲这一段，可以每次收缩后用 `max(cnt)` 重算真实的最多次数。26 个计数扫一遍，时间变成 O(26n)，窗口每一步都合法，不用再论证。
+
+## 代码
 
 ```python
-from collections import Counter
-
 def character_replacement(s: str, k: int) -> int:
-    cnt = [0] * 26
-    left = best = maxf = 0
+    cnt = [0] * 26                 # cnt[i]：窗口里第 i 个大写字母出现几次
+    left = best = maxf = 0         # maxf：历史上窗口里出现最多的字母次数，不回退
     for right, ch in enumerate(s):
         cnt[ord(ch) - 65] += 1
         maxf = max(maxf, cnt[ord(ch) - 65])
-        while right - left + 1 - maxf > k:
+        while right - left + 1 - maxf > k:   # 要改的字符数超过 k，左端右移
             cnt[ord(s[left]) - 65] -= 1
             left += 1
         best = max(best, right - left + 1)
     return best
+```
+
+`ord(ch) - 65` 把 `A` 到 `Z` 映射到 0 到 25（`ord("A")` 是 65）。
+
+已运行：2026-10-26，Python 3.13.17。输入是字母表 `ABC` 上长度 1 到 8 的全部字符串配每个 `0 <= k <= n`（83,652 组），加 5,000 组随机串（字母表 2 到 4 个字母，长度 1 到 14）。和暴力解（枚举所有子串）对拍，全部一致。`("AABABBA", 1)` 返回 4，`("AAB", 0)` 返回 2。下文说「同一批输入」就是这一批。
+
+## 复杂度
+
+时间 O(n)。`right` 和 `left` 各自只往右走，最多各走 n 步，每一步只做 O(1) 的更新。空间 O(1)，计数数组固定 26 位。
+
+## 易错点
+
+- 收缩条件里窗口长度写成 `right - left`，少了 1，相当于多允许了一次修改。2026-10-26 实测，同样输入 `"AB"`、`k = 0`，这样写返回 2，正确写法返回 1（窗口 `AB` 算出来 `1 − 1 = 0`，没触发收缩）。这类差一见 [[p:me/python-pitfalls]]。
+- 收缩时把 `maxf` 减 1 是错的，因为被移出的字母不一定是唯一出现最多的那个。只在「移出的字母计数等于 `maxf`」时减 1 也不行。2026-10-26 实测，同样输入 `"ABB"`、`k = 0`，这样写返回 1，正确写法返回 2：窗口 `AB` 收缩时移出的 `A` 计数等于 `maxf`，`maxf` 被减成 0，可 `B` 也出现 1 次，窗口被一路缩空，`BB` 就漏掉了。要么保留旧值并讲清为什么对（见「思路」），要么每次重新扫描 26 个计数。
+- 这题因为 `maxf` 不减小，每次最多只需要收缩一格，所以很多题解写的是 `if`，结果和 `while` 一样。340、904 这类求最长的题照抄 `if` 也能得到对的长度（2026-10-26 在 340 上穷举 `abc` 上长度 1 到 8 的字符串和 k = 0 到 3 验证过），因为窗口长度只在合法时才涨。但用了 `if`，窗口在中间某些步可能不合法，题目要用的是每一步的窗口本身时就会错。比如 209 求和至少为 target 的最短子数组，`target = 7`、`nums = [2, 3, 1, 2, 4, 3]` 时 `if` 返回 4，`while` 返回 2（2026-10-26 实测）。所以养成写 `while` 的习惯更安全（[[p:me/python-pitfalls]] 的「while 和 if」）。
+
+## Follow-up
+
+### 最长的合法子串有几个（Temu 二面考过）
+
+先用原题求出最长长度 `L`，再用固定长度 `L` 的窗口扫一遍，数满足 `L - 窗口内最多字母次数 <= k` 的窗口。先和面试官对齐「个数」按起点不同算还是按内容去重。去重就把合法窗口的子串放进 set。
+
+> [!say] For the count variant, I first get the max length L with the usual window, then slide a fixed window of size L and count how many of those windows are valid.
+
+这样数是对的，因为最长的合法子串长度都是 `L`，定长窗口把每个长度为 `L` 的子串恰好看一次，每次用真实的最多次数判一次合法。不能在原题那一遍循环里按「窗口长度等于 `L`」去数，因为 `maxf` 不回退时这样的窗口可能不合法（「思路」里 `AAB` 的 `AB` 就是），会被多数进来。
+
+```python
+from collections import Counter
 
 def count_longest(s: str, k: int) -> int:
@@ -57,5 +89,5 @@
         cnt[ch] += 1
         if i >= L:
-            cnt[s[i - L]] -= 1
+            cnt[s[i - L]] -= 1            # 定长窗口：移出最左边的字母
         if i >= L - 1 and L - max(cnt.values()) <= k:
             res += 1
@@ -63,5 +95,32 @@
 ```
 
-已运行：2026-10-17 用 2,000 组随机串和暴力解对拍，长度和个数都一致。例：`("AABABBA", 1)` → 长度 4、个数 2（`AABA`、`ABBA`）。时间 O(26n)。
+已运行：2026-10-26，同一批输入，和暴力解（按起点数长度为最长长度的合法子串）对拍，全部一致。`("AABABBA", 1)` 返回 2（`AABA` 和 `BABB`）。代价是多扫一遍，时间 O(26n)，`max(cnt.values())` 每次最多看 26 个计数。空间 O(1)。按内容去重时 set 里最多放 n 个长度为 `L` 的子串，空间 O(nL)。
 
-> [!say] For the count variant, I first get the max length L with the usual window, then slide a fixed window of size L and count how many of those windows are valid.
+### 输出所有的替换组合（Temu 2026-10-21 第二轮）
+
+现有资料只写了「要求输出所有的替换组合」，题面是中文、样例不够。下面这些要先问清：
+
+- 输出的是最长那几个窗口的修改方案，还是修改后得到的字符串？
+- 同一个窗口能改成不止一种字母时（`"AB"`、`k = 1` 可以改成 `AA` 也可以改成 `BB`），算一种还是两种？
+- 只输出最长的，还是所有合法窗口都要？
+- 修改方案用下标表示，还是用改完的字符串表示？
+- 目标字母能不能是窗口里没出现过的字母？`k >= L` 时 26 个字母都行，比如 `("A", 1)` 可以改成 `B` 到 `Z` 任何一个。下面的代码只考虑窗口里出现过的字母，这种情况只输出 1 个方案，要 26 个都列的话把 `sorted(set(window))` 换成 26 个字母。
+
+【推断】一种自然的理解：对每个长度为 `L` 的窗口、每个窗口里出现过的字母 `c`，如果把其余字母改成 `c` 不超过 k 次，就输出（起点、目标字母、要改的下标）。它是对的，理由和上一条一样：最长的合法窗口长度都是 `L`，代码把每个长度为 `L` 的窗口和每个候选字母都试了一遍，要改的下标就是窗口里不等于 `c` 的位置，个数不超过 k 才输出。
+
+```python
+def longest_plans(s: str, k: int) -> list:
+    L = character_replacement(s, k)
+    plans = []
+    for start in range(len(s) - L + 1):
+        window = s[start:start + L]
+        for c in sorted(set(window)):
+            changes = [start + i for i, x in enumerate(window) if x != c]
+            if len(changes) <= k:
+                plans.append((start, c, changes))
+    return plans
+```
+
+已运行：2026-10-26，同一批输入，和暴力解（对每个最长窗口，试窗口里出现过的每个字母）对拍，全部一致。暴力解改成试全部 26 个字母时，有 10,665 组不一致，都是上面列的 `k >= L` 的情况，比如 `("A", 1)` 暴力解给 26 个方案，这段代码给 1 个。`("AABABBA", 1)` 返回 `[(0, 'A', [2]), (2, 'B', [3])]`，`("AB", 1)` 返回 `[(0, 'A', [1]), (0, 'B', [0])]`。
+
+代价是每个窗口都重新切片、对每个候选字母扫一遍，时间 O((n − L + 1) · L · 26)，最坏 O(26n²)。可以先在定长窗口上维护 26 个计数，每个窗口 O(26) 判出哪些字母合法，只对合法的（窗口、字母）再扫一遍窗口写下标，时间变成 O(26n + 方案数 · L)。只要方案个数时不用写下标，总共 O(26n)。
更新题目 424. Longest Repeating Character Replacement

body

meta
