LeetCode 395中等分治/滑动窗口
至少有 K 个重复字符的最长子串 图解题解
这道题到底在问什么
给定小写字符串 s 和整数 k,返回最长子串的长度,要求该子串中每个出现的字符都至少出现 k 次。
- 输入
- s="aaabb", k=3
- 输出
- 3 (aaa 满足:每个字符都 ≥3 次)
最优解：一步一步想明白
- 3记住这句:「固定不同字符数 target → 窗口单调 → 能滑」。下面挑 target=1、target=2 两趟演给你看。
- 4第 1 趟:target=1,只允许窗口里有 1 种字符,且这一种要出现 ≥ 2 次。盯住右上角 count 面板和 unique/enough。
- 5右指针到第 0 位 'a',窗口里现在有 1 种不同字符。没超 target 1,再看是不是每种都够 2 次。
- 6右指针到第 1 位 'b',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
- 7左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
- 8右指针到第 2 位 'a',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
- 9左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
- 10右指针到第 3 位 'b',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
- 11左指针逐格右移 1 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
- 12右指针到第 4 位 'b',窗口里现在有 1 种不同字符。没超 target 1,再看是不是每种都够 2 次。
- 13这个窗口里 1 种字符每一种都到了至少 2 次(enough 也等于 1),合法!长度 2。比之前长,刷新最长 = 2。
- 14右指针到第 5 位 'c',窗口里现在有 2 种不同字符。超过 target 1 了,下一步左缩。
- 15左指针逐格右移 2 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 1,正好等于 target 1。
- 16第 2 趟:target=2,允许窗口里有恰好 2 种不同字符,且这 2 种都要 ≥ 2 次。这一趟会找到答案。
- 17右指针到第 0 位 'a',窗口里现在有 1 种不同字符。没超 target 2,再看是不是每种都够 2 次。
- 18右指针到第 1 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
- 19右指针到第 2 位 'a',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
- 20右指针到第 3 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
- 21这个窗口里 2 种字符每一种都到了至少 2 次(enough 也等于 2),合法!长度 4。比之前长,刷新最长 = 4。
- 22右指针到第 4 位 'b',窗口里现在有 2 种不同字符。没超 target 2,再看是不是每种都够 2 次。
- 23这个窗口里 2 种字符每一种都到了至少 2 次(enough 也等于 2),合法!长度 5。比之前长,刷新最长 = 5。
- 24右指针到第 5 位 'c',窗口里现在有 3 种不同字符。超过 target 2 了,下一步左缩。
- 25左指针逐格右移 3 步,每移出一个字符就把它的计数减一,直到某种字符计数减到 0、不同字符数从超出值降回 2,正好等于 target 2。
- 26target=3 时要 a、b、c 三种各 ≥ 2 次,但 c 在 "ababbc" 里只出现 1 次,配不齐;target=4 到 26 则因为 s 总共只有 3 种字符、凑不出那么多种,都不可能。所以最长仍是 5,这两类不再逐帧演。
- 27综合所有 target,最长的合法子串是绿色这段 "ababb"(a 出现 2 次、b 出现 3 次,都 ≥ 2),长度 5。这就是答案。
⚠️ 容易写错的地方
✗ 错：直接对原问题滑窗
✓ 对：先固定「不同字符数 target」再滑
合法性不单调,固定 distinct 数后才能滑
✗ 错：只用 unique 判合法
✓ 对：同时维护 enough(达 k 次的种数)
种类数对还不够,enough 才保证每种 ≥ k 次
✗ 错：左缩时漏更新计数
✓ 对：移出字符跌破 k 减 enough、跌到 0 减 unique
计数维护错,判定全乱
完整代码（Python / C++ / Java）
Python
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 ansC++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0, n = s.size();
for (int target = 1; target <= 26; ++target) {
vector<int> count(26);
int left = 0, unique = 0, enough = 0;
for (int right = 0; right < n; ++right) {
int idx = s[right] - 'a';
if (count[idx]++ == 0) unique++;
if (count[idx] == k) enough++;
while (unique > target) {
int li = s[left++] - 'a';
if (count[li] == k) enough--;
if (--count[li] == 0) unique--;
}
if (unique == target && enough == target) ans = max(ans, right - left + 1);
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int longestSubstring(String s, int k) {
int ans = 0, n = s.length();
for (int target = 1; target <= 26; target++) {
int[] count = new int[26];
int left = 0, unique = 0, enough = 0;
for (int right = 0; right < n; right++) {
int idx = s.charAt(right) - 'a';
if (count[idx]++ == 0) unique++;
if (count[idx] == k) enough++;
while (unique > target) {
int li = s.charAt(left++) - 'a';
if (count[li] == k) enough--;
if (--count[li] == 0) unique--;
}
if (unique == target && enough == target) ans = Math.max(ans, right - left + 1);
}
}
return ans;
}
}复杂度
时间
O(26·n)=O(n)
字符集大小固定 26,外层至多 26 个 target,每个 target 内左右指针各扫一遍 O(n)
空间
O(1)
count 是固定 26 长的计数,unique/enough 几个标量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 至少有 K 个重复字符的最长子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题还有别的经典解法吗?+
有,分治:在整个串里找出那些出现次数 < k 的字符,它们绝不可能出现在答案子串里,于是用它们当分隔符把串切成若干段,对每段递归求解,取最大。分治和「枚举 distinct 数 + 滑窗」两种思路都是为了绕开「合法性不单调」这个障碍。
为什么外层枚举到 26 就够?+
字符集是小写字母,最多 26 种不同字符,所以一个合法窗口里的不同字符数只可能是 1 到 26。把每种可能的 target 都试一遍,就覆盖了所有情况。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 至少有 K 个重复字符的最长子串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。