教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解基于 AlgoNote 仓库的 0424. 替换后的最长重复字符 文档展开系统讲解如何用「不定长滑动窗口 字符频数统计」把 O(n³) 的暴力枚举优化到 O(n)。读完你将掌握滑动窗口最核心的「窗口合法性判定」技巧窗口长度 - 窗口内最大字符频数 ≤ k并能直接迁移到「最多替换 K 次使区间内元素一致」这一类问题如 LeetCode 1004的求解。题目信息题目编号0424LeetCode 424题目链接0424. 替换后的最长重复字符 - 力扣标签哈希表、字符串、滑动窗口难度中等题目大意描述给定一个仅由大写英文字母组成的字符串s以及一个整数k。可以将任意位置上的字符替换成另外的大写字母最多可替换k次。要求在进行上述操作后找到包含重复字母的最长子串长度。说明数据范围1 ≤ s.length ≤ 10^5s仅由大写英文字母组成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的所有子串对于每一个子串统计子串中出现次数最多的字符替换除它以外的字符k次维护最长子串的长度。但这样做的代价极高枚举子串的时间复杂度为 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 次即可使窗口内字符全部相同否则窗口不合法需要收缩左边界。这一判定正是 不定长度滑动窗口 的应用——窗口大小不固定通过左右指针动态调整维护满足条件的连续区间。算法步骤使用counts数组长度 26对应 26 个大写字母统计字母频数使用left、right双指针分别指向滑动窗口的首尾位置使用max_count维护窗口内出现次数最多的字符的次数。不断右移right指针增加滑动窗口的长度并同步更新counts与max_count。对于当前滑动窗口的子串如果right - left max_count k说明即使替换k次仍不能使当前窗口中的字符全部变为相同字符此时应将左边界left右移同时将原先左边界的字符频次减一。循环结束时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逐行解读代码作用counts [0 for _ in range(26)]频数统计数组下标0~25对应字母A~Z由于题目限定仅含大写字母用定长数组比哈希表更省内存、更快num_right ord(s[right]) - ord(A)将右指针字符映射为数组下标ord(A)的值为 65任何大写字母减 65 得到 0~25 的整数counts[num_right] 1右指针字符进入窗口频数加一max_count max(max_count, counts[num_right])更新窗口内最大字符频数只增不减if right - left max_count k:窗口合法性判定right - left此时是right自增后的新窗口长度若超过max_count k说明替换k次也无法让窗口内字符统一counts[num_left] - 1; left 1左指针右移一步把离开窗口的字符频数减一收缩窗口return right - left循环结束时窗口长度即为历史最大合法窗口长度注意由于每轮循环要么right右移窗口变大要么left右移窗口保持窗口长度right - left在整个过程中单调不减因此循环结束后直接返回right - left即可无需单独用变量记录最大值。示例推演s AABABBA, k 1right当前字符频数变化max_count判定right-left max_countkleft窗口0AA:111 ≤ 2不收缩0[0,0]1AA:222 ≤ 3不收缩0[0,1]2BB:123 ≤ 3不收缩0[0,2]3AA:334 ≤ 4不收缩0[0,3]4BB:235 4收缩1[1,4]5BB:336-15 4收缩2[2,5]6AA:237-25 4收缩3[3,6]循环结束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 的最长连续子数组长度。两题的对应关系如下维度0424 替换后的最长重复字符1004 最大连续 1 的个数 III输入仅含大写字母的字符串s仅含 0、1 的数组nums替换对象任意非多数派字符窗口内的 0窗口合法条件right - left ≤ max_count k0 的个数 ≤ k核心数据结构26 长度频数数组counts单个计数器zero_count1004 的题解代码见 max-consecutive-ones-iii.md同样采用「right 右移扩大窗口、不合法时 left 右移收缩窗口」的同一套框架只是把「最大频数」替换成了更简单的「0 的个数」判断。建议两题对照练习可以深刻理解滑动窗口的合法性条件是如何随着问题语义变化的。刷题定位与延伸学习在 滑动窗口题目列表 中本题被归入「不定长度窗口题目」类别与 0003. 无重复字符的最长子串、0159. 至多包含两个不同字符的最长子串、0340. 至多包含 K 个不同字符的最长子串 等题同属一族可以一并刷完形成体系。滑动窗口算法本身的通用定义与两种形态固定长度窗口、不定长度窗口的代码模板可参考仓库的 滑动窗口算法讲解内含不定长窗口的标准模板与「无重复字符的最长子串」例题。本题与 1004 的官方归类同样可在 题解总览 与 分类目录 中查证。总结「替换后的最长重复字符」是学习不定长滑动窗口时不可跳过的一道经典题其核心收获有三点把操作语义翻译成窗口条件题目允许替换k次等价于「窗口内非多数派字符数 ≤ k」即right - left ≤ max_count k用频数数组替代哈希表字符集已知且固定26 个大写字母时定长数组下标映射比哈希表更高效理解 max_count 只增不减的正确性滑动窗口求最长区间时允许窗口只扩张不收缩历史最大值可以作为合法性判定的保守依据这是复杂度从 O(n³) 降到 O(n) 的关键。掌握本题后面对「最多替换/翻转 K 次求最长一致区间」类问题如 1004、487只需调整窗口合法性条件的表达即可快速套用同一套模板。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 0424 最长重复字符替换Longest Repeating Character Replacement滑动窗口三步进阶与多语言实现解析LeetCode 0424 最长重复字符替换Longest Repeating Character Replacement滑动窗口三步进阶与多语言实现解析示例工程教程LeetCode 424 替换后的最长重复字符滑动窗口与最长连续 1 模型的两种解法详解LeetCode 424 替换后的最长重复字符滑动窗口与最长连续 1 模型的两种解法详解 导读 LeetCode 424 题《替换后的最长重复字符》Lo文档教程知识库codeforces-go 题解精讲LeetCode 2958「最多 K 次频率的最长子数组」——不定长滑动窗口的经典实战codeforces go 题解精讲LeetCode 2958「最多 K 次频率的最长子数组」——不定长滑动窗口的经典实战 本文以算法竞赛模板库 codefo科学计算上一篇Flair 情感分析实战指南使用预训练 sentiment 模型进行文本情感分类下一篇Vega 实战用 Faceted Group Mark 构建 Barley Trellis Plot 小多图创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考