LeetCode 395. 至少有 K 个重复字符的最长子串
题目描述
题意分析
在字符串中选择一个连续子串，使其中每一种出现过的字符都至少出现
k次，返回满足要求的最大长度。没有这样的非空子串时返回0。次数只在选中的子串内部统计，不能借用子串外的字符；没有出现的字符不需要满足次数要求。字符串只有小写英文字母，所以字符种类最多为
26。
解法：枚举字符种类数的滑动窗口
核心思路
[!blue]
不能直接把“有字符不足
k次”作为收缩条件：一个不达标的字符可能在继续右扩后凑够次数，此时提前删除左端就会丢掉答案。需要先固定另一个能指导收缩的条件，即窗口允许包含的字符种类数。枚举目标种类数
targetKinds，在这一轮始终把窗口实际种类数限制在它以内。右端加入字符；只有种类超限时，左端才不断移出字符。这与“至多包含固定种类字符”的窗口相同，左右端都只向前移动。用
unique统计出现过的种类数，valid统计频次已达到k的种类数。加入时，频次从零变一才增加unique，恰好从k - 1变为k才增加valid；移出时反过来，频次从k变为k - 1才减少valid，减到零才减少unique。只有unique == valid == targetKinds，才说明窗口中每类字符都达标。枚举种类数不会漏解。设最优子串包含
c类字符，在targetKinds = c的那一轮，右端到达它的末尾时，左端不必越过它的开头，因为该子串本身不超过种类限制。此时保留的更大窗口包含它，又不能多出新种类，所以各类次数也都不少于它，必能得到至少同样长的合法结果。每个目标种类数使用独立的频次和双指针状态，完整扫描一次字符串，最后取所有轮次的最大长度。
解题步骤
- 从
1到26枚举targetKinds，每轮清空频次数组，重置left、unique、valid。- 右端加入字符；首次出现时增加
unique，加入后频次恰好达到k时增加valid。- 当
unique > targetKinds时移出左端字符：移出前频次恰好为k，先减少valid；减到零时减少unique。- 种类不超限后，若
unique和valid都等于目标种类数，用当前窗口长度更新答案。- 完成所有轮次，返回最大长度。
代码实现
class Solution {
public int longestSubstring(String s, int k) {
int ans = 0;
for (int targetKinds = 1; targetKinds <= 26; targetKinds++) {
int[] count = new int[26];
int left = 0;
int unique = 0;
int valid = 0;
for (int right = 0; right < s.length(); right++) {
int idx = s.charAt(right) - 'a';
if (count[idx] == 0) {
unique++;
}
count[idx]++;
if (count[idx] == k) {
valid++;
}
while (unique > targetKinds) {
int remove = s.charAt(left) - 'a';
// 移出前恰好达标，减一后这类字符将不再满足频次要求。
if (count[remove] == k) {
valid--;
}
count[remove]--;
if (count[remove] == 0) {
unique--;
}
left++;
}
// 固定字符种类数后，窗口满足所有字符频次要求即可更新答案。
if (unique == targetKinds && valid == targetKinds) {
ans = Math.max(ans, right - left + 1);
}
}
}
return ans;
}
}
func longestSubstring(s string, k int) int {
ans := 0
for targetKinds := 1; targetKinds <= 26; targetKinds++ {
count := make([]int, 26)
left := 0
unique := 0
valid := 0
for right := 0; right < len(s); right++ {
idx := int(s[right] - 'a')
if count[idx] == 0 {
unique++
}
count[idx]++
if count[idx] == k {
valid++
}
for unique > targetKinds {
remove := int(s[left] - 'a')
// 移出前恰好达标，减一后这类字符将不再满足频次要求。
if count[remove] == k {
valid--
}
count[remove]--
if count[remove] == 0 {
unique--
}
left++
}
// unique 和 valid 同时达到目标，说明窗口内每种字符都至少 k 次。
if unique == targetKinds && valid == targetKinds {
if right-left+1 > ans {
ans = right - left + 1
}
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(26n)=O(n)$。每轮左右指针各移动至多
n次，总共枚举固定的26个目标种类数。- 空间复杂度：$O(1)$，频次数组长度固定为
26，其余是常数个计数和下标。
关键点总结
[!green]
- 先固定种类上限，让“种类超限就收缩”成为明确规则，再检查每类频次是否达标。
unique统计出现种类，valid统计达标种类，二者含义不能混用。- 达标计数只在跨越
k的阈值时变化，频次继续增长不代表新增一种字符。- 最优子串的种类数必然落在枚举范围内，对应那一轮能完整覆盖它。
补充解法：按不足次数的字符分治
核心思路
[!blue]
在当前区间内，若某个字符总共只出现了不足
k次，那么任何包含它的子串都不可能合法，因为缩小区间只会让它的次数更少。因此，这个字符的每次出现都可以作为分隔位置，答案必定位于分隔出来的某一个连续段内，不能跨过分隔位置。先统计当前区间频次，再在所有不足
k的字符处切分，递归求各段答案并取最大值。切分后的段必须重新计数，因为一种字符可能在原区间足够多，分到某个小段后却不再达标。如果没有不足次数的字符，整个区间已经合法，直接返回区间长度；若区间长度小于
k，其中任何非空子串都不可能达标，返回零。代码传递左右边界表示子串，不复制字符串。
解题步骤
- 用半开区间
[left, right)表示当前子问题；长度小于k时直接返回0。- 统计当前区间的各字符频次。
- 扫描区间，遇到频次小于
k的字符，就递归求它前面尚未处理的连续段，更新最大值，再跳过分隔字符。- 若整个扫描没有切分，返回当前区间长度。
- 否则递归处理最后一段，与已有结果取最大值返回。
代码实现
class Solution {
public int longestSubstring(String s, int k) {
return longest(s, 0, s.length(), k);
}
private int longest(String s, int left, int right, int k) {
if (right - left < k) {
return 0;
}
int[] count = new int[26];
for (int i = left; i < right; i++) {
count[s.charAt(i) - 'a']++;
}
int start = left;
int ans = 0;
for (int i = left; i < right; i++) {
if (count[s.charAt(i) - 'a'] < k) {
ans = Math.max(ans, longest(s, start, i, k));
start = i + 1;
}
}
if (start == left) {
return right - left;
}
return Math.max(ans, longest(s, start, right, k));
}
}
func longestSubstring(s string, k int) int {
return longestPart(s, 0, len(s), k)
}
func longestPart(s string, left int, right int, k int) int {
if right-left < k {
return 0
}
var count [26]int
for i := left; i < right; i++ {
count[s[i]-'a']++
}
start, ans := left, 0
for i := left; i < right; i++ {
if count[s[i]-'a'] < k {
candidate := longestPart(s, start, i, k)
if candidate > ans {
ans = candidate
}
start = i + 1
}
}
if start == left {
return right - left
}
candidate := longestPart(s, start, right, k)
if candidate > ans {
ans = candidate
}
return ans
}
复杂度分析
- 时间复杂度：$O(26n)=O(n)$。每层处理的各区间互不重叠，扫描总长度不超过
n；每次继续分治都会从下一层区间中排除至少一种字符，沿一条递归路径最多经历26次种类减少。- 空间复杂度：$O(1)$，相对于字符串长度
n而言，递归深度受固定字符集大小限制，每层只保留长为26的频次数组和下标；不复制子串。若将字符集大小记为 $C$，辅助空间上界为 $O(C^2)$。
关键点总结
[!green]
- 当前区间内次数不足的字符，无法被任何更小子串补足，因此可以安全作为分隔点。
- 子问题对应分隔后的连续段，答案取各段最大值，不能把不相邻的段相加。
- 每次递归重新计数，直到整个区间合法，或者短到不可能满足要求。
易错点总结
[!yellow]
- 发现某类字符暂时不足
k就立即收缩，忽略了继续扩张可能让它达标。- 每次加入后只要频次
>= k就增加valid，会重复计算同一种字符。- 移出字符后才判断旧频次是否等于
k，会错过刚刚失去达标资格的那一刻；应在减法前检查。- 用
unique >= targetKinds触发收缩，会把种类数恰好满足目标的窗口也移除。- 切换目标种类数后保留上一轮状态，使窗口计数与当前边界不一致。
- 分治时只用整个原串的频次，切分后的区间可能出现新的不足字符，必须在每个子问题重新统计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 同样统计窗口字符频次，但本题限制每个出现字符至少k次，不能直接照搬至多k种字符的单调收缩条件。 |
| 424. 替换后的最长重复字符 | 中等 | 同样利用窗口长度与频次，本题要求所有字符达下限，原题按替换预算统一成一个字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！