题目描述
思路解析动画文字版
记住这句:「固定不同字符数 target → 窗口单调 → 能滑」。下面挑 target=1、target=2 两趟演给你看。
第 1 趟:target=1,只允许窗口里有 1 种字符,且这一种要出现 ≥ 2 次。盯住右上角 count 面板和 unique/enough。
右指针到第 0 位 'a',窗口里现在有 1 种不同字符。没超 target 1,再看是不是每种都够 2 次。
右指针到第 1 位 'b',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
右指针到第 2 位 'a',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
右指针到第 3 位 'b',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
右指针到第 4 位 'b',窗口里现在有 1 种不同字符。没超 target 1,再看是不是每种都够 2 次。
这个窗口里 1 种字符每一种都到了至少 2 次(enough 也等于 1),合法!长度 2。比之前长,刷新最长 = 2。
右指针到第 5 位 'c',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
左指针逐格右移 2 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
第 2 趟:target=2,允许窗口里有恰好 2 种不同字符,且这 2 种都要 ≥ 2 次。这一趟会找到答案。
右指针到第 0 位 'a',窗口里现在有 1 种不同字符。没超 target 2,再看是不是每种都够 2 次。
右指针到第 1 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
右指针到第 2 位 'a',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
右指针到第 3 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
这个窗口里 2 种字符每一种都到了至少 2 次(enough 也等于 2),合法!长度 4。比之前长,刷新最长 = 4。
右指针到第 4 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
这个窗口里 2 种字符每一种都到了至少 2 次(enough 也等于 2),合法!长度 5。比之前长,刷新最长 = 5。
右指针到第 5 位 'c',窗口里现在有 3 种不同字符。超过 target 2 了,下一步左缩。
左指针逐格右移 3 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 2,正好等于 target 2。
target=3 时要 a、b、c 三种各 ≥ 2 次,但 c 在 "ababbc" 里只出现 1 次,配不齐;target=4 到 26 则因为 s 总共只有 3 种字符、凑不出那么多种,都不可能。所以最长仍是 5,这两类不再逐帧演。
综合所有 target,最长的合法子串是绿色这段 "ababb"(a 出现 2 次、b 出现 3 次,都 ≥ 2),长度 5。这就是答案。
边界:k=1 整串过、每种都不足 k 次则为 0。
面试常考:对比分治解法,以及为什么 target 上界是 26。
参考代码
class Solution: def longestSubstring(self, s: str, k: int) -> int: ans = 0 for target in range(1, 27): count = [0] * 26 left = unique = enough = 0 for right, ch in enumerate(s): idx = ord(ch) - 97 if count[idx] == 0: unique += 1 count[idx] += 1 if count[idx] == k: enough += 1 while unique > target: li = ord(s[left]) - 97 if count[li] == k: enough -= 1 count[li] -= 1 if count[li] == 0: unique -= 1 left += 1 if unique == target and enough == target: ans = max(ans, right - left + 1) return ans复杂度
- 时间：O(26·n)=O(n)，字符集大小固定 26,外层至多 26 个 target,每个 target 内左右指针各扫一遍 O(n)
- 空间：O(1)，count 是固定 26 长的计数,unique/enough 几个标量
易错点
面试追问把动画讲成自己的话
追问这题还有别的经典解法吗?
追问为什么外层枚举到 26 就够?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题