企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇题解基于 AlgoNote 仓库的 0424. 替换后的最长重复字符 文档展开，系统讲解如何用「不定长滑动窗口 + 字符频数统计」把 O(n³) 的暴力枚举优化到 O(n)。读完你将掌握滑动窗口最核心的「窗口合法性判定」技巧（窗口长度 - 窗口内最大字符频数 ≤ k），并能直接迁移到「最多替换 K 次使区间内元素一致」这一类问题（如 LeetCode 1004）的求解。

题目信息

• 题目编号：0424（LeetCode 424）
• 题目链接：0424. 替换后的最长重复字符 - 力扣
• 标签：哈希表、字符串、滑动窗口
• 难度：中等

题目大意

描述：给定一个仅由大写英文字母组成的字符串s，以及一个整数k。可以将任意位置上的字符替换成另外的大写字母，最多可替换k次。

要求：在进行上述操作后，找到包含重复字母的最长子串长度。

说明（数据范围）：

• 1 ≤ s.length ≤ 10^5
• s仅由大写英文字母组成
• 0 ≤ k ≤ s.length

示例 1：

输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。 可能存在其他的方法来得到同样的结果。

先看暴力解法：为什么 O(n³) 会超时

暴力求法的思路很直观：枚举字符串s的所有子串，对于每一个子串：

1. 统计子串中出现次数最多的字符；
2. 替换除它以外的字符k次；
3. 维护最长子串的长度。

但这样做的代价极高：枚举子串的时间复杂度为 O(n²)，统计出现次数最多的字符和替换字符的时间复杂度为 O(n)，且两者属于平行处理，总体时间复杂度为 O(n³)。在s.length上限为 10⁵ 的约束下（见 题解文档），O(n³) 的暴力做法必然超时，必须寻找线性算法。

核心思路：不定长滑动窗口

窗口合法性的关键不等式

替换k次后，一个子串能否全部变成同一个字符，取决于两个量：

• 子串长度right - left；
• 子串中出现次数最多的字符的次数max_count。

子串中「非多数派字符」的数量为(right - left) - max_count。只要这个数量不超过k，就可以通过最多k次替换，把整个子串变成由同一个字符构成的字符串。

于是得到窗口的合法性判定：

right - left ≤ max_count + k时，窗口合法（替换 k 次即可使窗口内字符全部相同）；否则窗口不合法，需要收缩左边界。

这一判定正是 不定长度滑动窗口 的应用——窗口大小不固定，通过左右指针动态调整，维护满足条件的连续区间。

算法步骤

1. 使用counts数组（长度 26，对应 26 个大写字母）统计字母频数；使用left、right双指针分别指向滑动窗口的首尾位置；使用max_count维护窗口内出现次数最多的字符的次数。
2. 不断右移right指针，增加滑动窗口的长度，并同步更新counts与max_count。
3. 对于当前滑动窗口的子串，如果right - left > max_count + k，说明即使替换k次仍不能使当前窗口中的字符全部变为相同字符，此时应将左边界left右移，同时将原先左边界的字符频次减一。
4. 循环结束时，right - left即为所求的最长重复字符子串长度。

一个容易忽略的关键点：max_count 从不缩水

在标准实现中，收缩左边界时不会重新计算max_count（即便被移出的恰好是出现最多的字符，max_count也不会减小）。这是有意为之的：

• max_count表示的是历史出现过的最大的「窗口内多数派字符频数」；
• 窗口合法性判定的目标并不是让每个时刻的窗口都合法，而是让窗口只扩大、不缩小；
• 当窗口不合法时，左指针移动一步，窗口长度保持不变；当窗口合法时，右指针移动一步，窗口长度加一。因此right - left单调不减，最终值就是所有合法窗口中的最大长度，即问题的答案。

这种做法牺牲了max_count的实时精确性，换来的是 O(n) 的单次扫描复杂度，是本题最精妙的工程化取舍。

完整代码与逐行解读

以下是 题解文档 给出的标准实现：

class Solution: def characterReplacement(self, s: str, k: int) -> int: max_count = 0 left, right = 0, 0 counts = [0 for _ in range(26)] while right < len(s): num_right = ord(s[right]) - ord('A') counts[num_right] += 1 max_count = max(max_count, counts[num_right]) right += 1 if right - left > max_count + k: num_left = ord(s[left]) - ord('A') counts[num_left] -= 1 left += 1 return right - left

逐行解读：

注意：由于每轮循环要么right右移（窗口变大），要么left右移（窗口保持），窗口长度right - left在整个过程中单调不减，因此循环结束后直接返回right - left即可，无需单独用变量记录最大值。

示例推演：s = "AABABBA", k = 1

循环结束，right - left = 7 - 3 = 4，与示例输出一致。窗口[3,6]对应子串"BBBA"，其中B出现 3 次，替换 1 次即可得到"BBBB"，长度为 4。

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度。right与left各至多移动 n 次，全程只扫描一遍字符串，不存在嵌套循环。
• 空间复杂度：O(|Σ|)，其中 Σ 是字符集。本题|Σ| = 26，即counts数组大小固定为 26，与字符串长度无关。

作为对比：暴力枚举的时间复杂度 O(n³) 在 n = 10⁵ 时完全不可行，而滑动窗口方案将其压缩到 O(n)，这正是「窗口合法性判定 + 只增不减的 max_count」带来的收益。

同类题型迁移：LeetCode 1004「最大连续 1 的个数 III」

「替换后的最长重复字符」是「最多替换 K 次使区间内元素一致」问题族的模板题。仓库中 1004. 最大连续 1 的个数 III 是它的直接变体：给定一个由 0、1 组成的数组，最多可以把k个 0 变成 1，返回仅包含 1 的最长连续子数组长度。

两题的对应关系如下：

1004 的题解代码（见 max-consecutive-ones-iii.md）同样采用「right 右移扩大窗口、不合法时 left 右移收缩窗口」的同一套框架，只是把「最大频数」替换成了更简单的「0 的个数」判断。建议两题对照练习，可以深刻理解滑动窗口的合法性条件是如何随着问题语义变化的。

刷题定位与延伸学习

• 在 滑动窗口题目列表 中，本题被归入「不定长度窗口题目」类别，与 0003. 无重复字符的最长子串、0159. 至多包含两个不同字符的最长子串、0340. 至多包含 K 个不同字符的最长子串 等题同属一族，可以一并刷完形成体系。
• 滑动窗口算法本身的通用定义与两种形态（固定长度窗口、不定长度窗口）的代码模板，可参考仓库的 滑动窗口算法讲解（内含不定长窗口的标准模板与「无重复字符的最长子串」例题）。
• 本题与 1004 的官方归类同样可在 题解总览 与 分类目录 中查证。

总结

「替换后的最长重复字符」是学习不定长滑动窗口时不可跳过的一道经典题，其核心收获有三点：

1. 把操作语义翻译成窗口条件：题目允许替换k次，等价于「窗口内非多数派字符数 ≤ k」，即right - left ≤ max_count + k；
2. 用频数数组替代哈希表：字符集已知且固定（26 个大写字母）时，定长数组下标映射比哈希表更高效；
3. 理解 max_count 只增不减的正确性：滑动窗口求最长区间时，允许窗口只扩张不收缩，历史最大值可以作为合法性判定的保守依据，这是复杂度从 O(n³) 降到 O(n) 的关键。

掌握本题后，面对「最多替换/翻转 K 次求最长一致区间」类问题（如 1004、487），只需调整窗口合法性条件的表达即可快速套用同一套模板。

• 教程
• 文档
• 知识库