LeetCode 395. 至少有 K 个重复字符的最长子串
目录
题目描述
题意分析
在字符串
s中找一段连续子串，要求这段子串里凡是出现过的字符，出现次数都不少于k，返回满足条件的最长子串长度。注意条件只约束「出现过的字符」，没出现的字符不参与判断，所以合法子串包含几种字符是自由的。约束信号很明确：
s只由小写字母构成，字符集大小固定为 26，这是一个常数，意味着「按字符种类数枚举」这种在一般字母表下不可接受的做法，在这里只会带来常数倍开销。另一个关键信号是「至少
k次」这个条件不具备单调性：子串变长，某个原本不达标的字符可能达标，也可能引入新的不达标字符，所以合法性既不随长度单调变好也不单调变差。这一点直接决定了不能对着原串裸跑一个双指针。边界要留意：
k <= 1时整个串本身就合法，答案是s.length()；k大于s的长度时不存在任何合法子串，答案为 0；s为空串时答案为 0。此外「至少k次」允许某个字符出现远超k次，不要错读成「恰好k次」。
解法：枚举字符种类数的滑动窗口
核心思路
本题不能直接用一次滑动窗口：右端加入新字符可能让窗口不合法，继续扩张又可能让该字符达到
k次重新合法，因此“不合法就收缩”没有单调依据。小写字母只有 26 种，可以枚举窗口应包含的字符种类数
targetKinds。固定这个值后，窗口一旦出现超过targetKinds种字符就必须收缩，双指针有了明确规则。最优子串一定含有某个确定的种类数，因此 1 到 26 的某一轮必然覆盖它。每轮维护
count、窗口内不同字符数unique，以及出现次数至少为k的字符数valid。收缩结束后始终有unique <= targetKinds；当unique == valid == targetKinds时，窗口内出现过的每个字符都达标，窗口合法。
valid只在频次跨过阈值时变化：加入后频次恰为k才加一；移出前频次恰为k才减一。这样每种字符只会被计入一次，判定始终与频次数组一致。
解题步骤
- 从 1 到 26 枚举
targetKinds，每轮重置窗口状态。- 右指针加入字符：频次从 0 变 1 时增加
unique，频次达到k时增加valid。- 当
unique > targetKinds时移动左指针；字符从达标变为不达标时减少valid，频次归零时减少unique。- 若
unique == targetKinds && valid == targetKinds，用当前窗口长度更新答案。以
s = "ababbc"、k = 2为例。在targetKinds = 2这一轮，窗口扩到ababb时，a出现 2 次、b出现 3 次，unique = valid = 2，答案更新为 5；再加入c后种类数超限，收缩后不再满足所有字符至少出现 2 次。
代码实现
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次。- 空间复杂度：$O(1)$，频次数组长度固定为 26。
关键点总结
- 原条件不单调；固定字符种类数后，才有“种类超限就收缩”的单调规则。
- 枚举不会漏解，因为任何候选子串都有唯一确定的字符种类数。
unique管“出现过”，valid管“频次达标”，两者相等才说明窗口合法。- 阈值计数只在跨过
k时更新，避免重复统计同一字符。
易错点总结
- 直接按“有字符不足
k就收缩”没有单调性；"aaabb"、k = 3的答案是 3。- 右扩时用
count[idx] >= k增加valid，会让同一字符被重复计数；只能在== k时增加。- 左缩后再判断
count[remove] == k会错过从k降到k-1的瞬间，应在减法前判断。- 收缩条件应是
unique > targetKinds，写成>=会把字符种类数恰好合适的窗口也移除。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 3. 无重复字符的最长子串 | 中等 | 合法性天然单调，是可以直接裸跑双指针的对照组 |
| 76. 最小覆盖子串 | 困难 | 求最短而非最长，收缩发生在窗口已合法之后 |
| 159. 至多包含两个不同字符的最长子串 | 中等 | 种类数上界由题目直接给定，无需外层枚举 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 本题内层单轮的原型，只有种类数约束、没有频次下限约束 |
| 424. 替换后的最长重复字符 | 中等 | 约束换成「可替换次数」，靠历史最大频次维持窗口不回缩 |
| 1004. 最大连续 1 的个数 III | 中等 | 把频次条件简化为翻转次数上限，是双指针单调性的最简演示 |