LeetCode 424中等滑动窗口
替换后的最长重复字符 图解题解
最多换 k 个字符，能凑出多长的同字符串？一把伸缩雨伞帮你数清楚。
像在一排彩色方块上撑一把雨伞：伞下最多允许 k 块杂色（替换掉），其余全是主色。右端一格格扩开，若杂色数超过 k，就从左端缩一格让伞重新合法；否则继续右扩。全程只数「窗口里出现最多的那种颜色」，用窗口长度减它就是要替换的数。
这道题到底在问什么
给定字符串 s 和整数 k，最多替换 k 个字符，求替换后「全是同一字母」的最长连续子串长度。
- 输入
- s="AABABBA", k=1
- 输出
- 4
最优解：一步一步想明白
- 3记住这条判定，下面每一帧都在套它。
- 4右指针 r 扩到下标 0，把字符 'A' 纳入窗口。
- 5'A' 计数 +1，窗口内最多字母出现 1 次。此时需替换 1−1=0 个字符。
- 6当前窗口 [0, 0] 长度 1 合法，更新最长答案 result=1。
- 7右指针 r 扩到下标 1，把字符 'A' 纳入窗口。
- 8'A' 计数 +1，窗口内最多字母出现 2 次。此时需替换 2−2=0 个字符。
- 9当前窗口 [0, 1] 长度 2 合法，更新最长答案 result=2。
- 10右指针 r 扩到下标 2，把字符 'B' 纳入窗口。
- 11'B' 计数 +1，窗口内最多字母出现 2 次。此时需替换 3−2=1 个字符。
- 12当前窗口 [0, 2] 长度 3 合法，更新最长答案 result=3。
- 13右指针 r 扩到下标 3，把字符 'A' 纳入窗口。
- 14'A' 计数 +1，窗口内最多字母出现 3 次。此时需替换 4−3=1 个字符。
- 15当前窗口 [0, 3] 长度 4 合法，更新最长答案 result=4。
- 16右指针 r 扩到下标 4，把字符 'B' 纳入窗口。
- 17'B' 计数 +1，窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
- 18需替换数超过 k=1，左指针右移，移出 'A'，窗口收缩到 [1, 4]。
- 19当前窗口 [1, 4] 长度 4 合法，更新最长答案 result=4。
- 20右指针 r 扩到下标 5，把字符 'B' 纳入窗口。
- 21'B' 计数 +1，窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
- 22需替换数超过 k=1，左指针右移，移出 'A'，窗口收缩到 [2, 5]。
- 23当前窗口 [2, 5] 长度 4 合法，更新最长答案 result=4。
- 24右指针 r 扩到下标 6，把字符 'A' 纳入窗口。
- 25'A' 计数 +1，窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
- 26需替换数超过 k=1，左指针右移，移出 'B'，窗口收缩到 [3, 6]。
- 27当前窗口 [3, 6] 长度 4 合法，更新最长答案 result=4。
- 28整条字符串扫完，最长可行窗口（已标绿）长度就是答案 4。
⚠️ 容易写错的地方
✗ 错：缩左时回退 maxCount
✓ 对：maxCount 不必减回
答案只取最长，历史峰值不会让窗口缩得过头
✗ 错：判定写成长度 > k
✓ 对：判定是「窗口长 − maxCount > k」
要替换的只有非最多字母那部分
✗ 错：窗口收缩时漏减计数
✓ 对：移出 s[l] 必须计数 −1
否则计数失真、maxCount 偏大
完整代码（Python / C++ / Java）
Python
def characterReplacement(s, k):
cnt = {}
maxCount = l = res = 0
for r, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
maxCount = max(maxCount, cnt[ch])
while (r - l + 1) - maxCount > k:
cnt[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return resC++
int characterReplacement(string s, int k){
vector<int> cnt(26, 0);
int maxCount = 0, l = 0, res = 0;
for(int r = 0; r < s.size(); r++){
cnt[s[r]-'A']++;
maxCount = max(maxCount, cnt[s[r]-'A']);
while((r - l + 1) - maxCount > k){
cnt[s[l]-'A']--; l++;
}
res = max(res, r - l + 1);
}
return res;
}Java
int characterReplacement(String s, int k){
int[] cnt = new int[26];
int maxCount = 0, l = 0, res = 0;
for(int r = 0; r < s.length(); r++){
cnt[s.charAt(r) - 'A']++;
maxCount = Math.max(maxCount, cnt[s.charAt(r) - 'A']);
while((r - l + 1) - maxCount > k){
cnt[s.charAt(l) - 'A']--; l++;
}
res = Math.max(res, r - l + 1);
}
return res;
}复杂度
时间
O(n)
左右指针各最多走 n 步
空间
O(1)
计数表至多 26 个字母
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 替换后的最长重复字符 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 maxCount 不用在缩窗时减回去？+
我们只关心历史出现过的最长合法窗口。maxCount 偏大只会让窗口不再扩张、不会缩短，对最终最大值无影响。
换成可含小写、数字等任意字符怎么办？+
把固定 26 长度的计数数组换成哈希表即可，逻辑不变。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 替换后的最长重复字符 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。