LeetCode 424中等滑动窗口
替换后的最长重复字符 图解题解
最多换 k 个字符，能凑出多长的同字符串？一把伸缩雨伞帮你数清楚。
像在一排彩色方块上撑一把雨伞：伞下最多允许 k 块杂色（替换掉），其余全是主色。右端一格格扩开，若杂色数超过 k，就从左端缩一格让伞重新合法；否则继续右扩。全程只数「窗口里出现最多的那种颜色」，用窗口长度减它就是要替换的数。
这道题到底在问什么
给一个字符串和 k，最多替换 k 个字符，求能变成同字符子串的最长长度。
- 示例
- s="AABABBA", k=1 → 4
先想最直接的笨办法
枚举每个子串再数频率会反复扫描。（动画第 3 步）
最优解：一步一步想明白
- 3枚举每个子串再数频率会反复扫描。
- 4窗口长度减去窗口内最高频字符数，就是需要替换的字符数；超过 k 才缩左边。
- 5滑动窗口：窗口里保留出现最多的字符，其余全替换。要替换的数 = 窗口长 − 最高频，只要 ≤ k=1 就合法。
- 6窗口 AAB：最高频 A×2，要替换 = 3−2 = 1 ≤ 1 → 合法，长度 3。
- 7右扩成 AABA：最高频 A×3，要替换 = 4−3 = 1 ≤ 1 → 合法，长度 4(目前最长)。
- 8关键帧：再扩成 AABAB → 最高频 A×3，要替换 = 5−3 = 2 ＞ k=1 → 不合法！左指针右移收缩窗口，直到重新合法。
- 9l 右移一格、对应字符计数减一，窗口缩到 ABAB(长 4)重新合法，继续右扩。整个过程最长合法窗口 = 4。
- 10答案 4：把 AABA 里的 1 个 B 替换成 A → AAAA，长度 4。
- 13一句话记住：窗口长度减去窗口内最高频字符数，就是需要替换的字符数；超过 k 才缩左边。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=slidingwindow 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：枚举每个子串再数频率
✓ 对：滑动窗口一遍 O(n)
枚举子串是 O(n²);窗口法只扫一遍。
✗ 错：窗口非法时清空重来
✓ 对：只把左指针右移一格
窗口单调右滑，左指针只进不退，均摊 O(n)。
✗ 错：maxCnt 收缩时纠结要不要减
✓ 对：不用减(只增不减也对)
答案只在窗口变长时刷新;maxCnt 偏大只让窗口暂时不缩，不影响最终最大值。
完整代码（Python / C++ / Java）
Python
class Solution:
def characterReplacement(self, s, k):
cnt, l, best, maxCnt = {}, 0, 0, 0
for r, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
maxCnt = max(maxCnt, cnt[ch])
while r - l + 1 - maxCnt > k:
cnt[s[l]] -= 1; l += 1
best = max(best, r - l + 1)
return bestC++
class Solution { public:
int characterReplacement(string s, int k) {
vector<int> cnt(26); int l=0,best=0,maxCnt=0;
for (int r=0;r<s.size();r++) {
maxCnt=max(maxCnt, ++cnt[s[r]-'A']);
while (r-l+1-maxCnt > k) cnt[s[l++]-'A']--;
best=max(best, r-l+1);
} return best;
}
};Java
class Solution {
public int characterReplacement(String s, int k) {
int[] cnt = new int[26]; int l=0,best=0,maxCnt=0;
for (int r=0;r<s.length();r++) {
maxCnt = Math.max(maxCnt, ++cnt[s.charAt(r)-'A']);
while (r-l+1-maxCnt > k) cnt[s.charAt(l++)-'A']--;
best = Math.max(best, r-l+1);
} return best;
}
}套路模板 · 滑动窗口(最高频)
# 替换后最长重复字符骨架
l = maxCnt = best = 0; cnt = {}
for r, ch in enumerate(s):
cnt[ch] += 1; maxCnt = max(maxCnt, cnt[ch])
while (r - l + 1) - maxCnt > k: # 要替换的 ＞ k → 收缩
cnt[s[l]] -= 1; l += 1
best = max(best, r - l + 1)
return best复杂度
时间复杂度
O(n)
左右指针各只前进 n 步
空间复杂度
O(1)
计数用固定 26 大小的数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 替换后的最长重复字符 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
滑动窗口:维护「窗口长 − 最高频字符数 = 要替换的数」，≤ k 则合法;右扩 r，超过 k 就右移 l 收缩，全程记最长合法窗口。
这道题为什么用「滑动窗口」，换最直接的暴力解会差在哪？+
滑动窗口抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。