题目描述
思路解析动画文字版
记住这条判定,下面每一帧都在套它。
右指针 r 扩到下标 0,把字符 'A' 纳入窗口。
'A' 计数 +1,窗口内最多字母出现 1 次。此时需替换 1−1=0 个字符。
当前窗口 [0, 0] 长度 1 合法,更新最长答案 result=1。
右指针 r 扩到下标 1,把字符 'A' 纳入窗口。
'A' 计数 +1,窗口内最多字母出现 2 次。此时需替换 2−2=0 个字符。
当前窗口 [0, 1] 长度 2 合法,更新最长答案 result=2。
右指针 r 扩到下标 2,把字符 'B' 纳入窗口。
'B' 计数 +1,窗口内最多字母出现 2 次。此时需替换 3−2=1 个字符。
当前窗口 [0, 2] 长度 3 合法,更新最长答案 result=3。
右指针 r 扩到下标 3,把字符 'A' 纳入窗口。
'A' 计数 +1,窗口内最多字母出现 3 次。此时需替换 4−3=1 个字符。
当前窗口 [0, 3] 长度 4 合法,更新最长答案 result=4。
右指针 r 扩到下标 4,把字符 'B' 纳入窗口。
'B' 计数 +1,窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
需替换数超过 k=1,左指针右移,移出 'A',窗口收缩到 [1, 4]。
当前窗口 [1, 4] 长度 4 合法,更新最长答案 result=4。
右指针 r 扩到下标 5,把字符 'B' 纳入窗口。
'B' 计数 +1,窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
需替换数超过 k=1,左指针右移,移出 'A',窗口收缩到 [2, 5]。
当前窗口 [2, 5] 长度 4 合法,更新最长答案 result=4。
右指针 r 扩到下标 6,把字符 'A' 纳入窗口。
'A' 计数 +1,窗口内最多字母出现 3 次。此时需替换 5−3=2 个字符。
需替换数超过 k=1,左指针右移,移出 'B',窗口收缩到 [3, 6]。
当前窗口 [3, 6] 长度 4 合法,更新最长答案 result=4。
整条字符串扫完,最长可行窗口(已标绿)长度就是答案 4。
边界先想清。
两个高频追问。
参考代码
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 res复杂度
- 时间:O(n),左右指针各最多走 n 步
- 空间:O(1),计数表至多 26 个字母
易错点
面试追问把动画讲成自己的话
追问为什么 maxCount 不用在缩窗时减回去?
追问换成可含小写、数字等任意字符怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
字符串的排列
LeetCode 567 · 中等 · 沿着 滑动窗口 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题