LeetCode 340. 至多包含 K 个不同字符的最长子串
目录
题目描述
题意分析
给一个字符串
s和一个整数k，要求返回一个长度最大的子串的长度，这个子串里出现的不同字符种类数不超过k。注意求的是长度这个数字，不是子串本身。「子串」这个词是第一个关键信号：它指的是连续的一段，不是可以跳着挑的子序列。连续意味着一段区间由左右两个端点唯一确定，也意味着「在已有区间上往右扩一位」这个操作是有意义的。
第二个关键信号是「至多 $k$ 种字符」这个条件的性质：它是一个判非法的条件，而且是单调的——区间越长，包含的字符种类只会不减；一旦某个区间已经有超过 $k$ 种字符，任何包含它的更长区间必然也超过 $k$ 种。换句话说，条件被破坏之后，靠继续往右扩是永远救不回来的，只能从左边缩。这正是可变长度窗口能成立的前提：右端负责试探、左端负责在越界时把窗口拉回合法。
边界要留意几处：
k可能等于 0，此时任何非空子串都不合法，答案是 0；k大到超过字符串里的字符种类数时，整个字符串都合法，答案就是s的长度；s可能为空。另外题目并没有限定字符集是小写字母，写代码时不要想当然地开一个长度 26 的数组。
解法：滑动窗口维护字符种类
核心思路
枚举所有子串至少需要 $O(n^2)$。本题的约束具有单调性：窗口一旦包含超过 $k$ 种字符，继续右扩不可能恢复合法，只能移动左端点，因此适合可变长度滑动窗口。
右指针负责加入字符；不同字符数超限时，左指针不断移出字符直到窗口重新合法。左右指针都只向右移动，不会重复枚举同一段区间。
哈希表记录窗口内每个字符的出现次数，并且只保留正计数；计数降为 0 时必须删除键，这样表的大小才等于当前字符种类数。
不变量是：收缩结束后
[left, right]至多包含 $k$ 种字符，并且是以right结尾的最长合法窗口。因为再向左多保留一个字符时窗口仍处于超限状态，所以此时才能用窗口长度更新答案。
解题步骤
k == 0时直接返回 0；初始化计数表、左端点和答案。- 右端点逐字符扩张，并将新字符计数加一。
- 当表中字符种类超过 $k$ 时，循环移动左端点；移出字符的计数降为 0 就删除该键。
- 窗口恢复合法后，用
right - left + 1更新最大长度。例如
s = "eceba"、k = 2：窗口先扩到"ece"，答案更新为 3；加入b后种类数变成 3，连续移出e、c才恢复合法。之后加入a也需要收缩，最终答案仍为 3。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (k == 0) {
return 0;
}
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
char in = s.charAt(right);
count.put(in, count.getOrDefault(in, 0) + 1);
while (count.size() > k) {
char out = s.charAt(left++);
count.put(out, count.get(out) - 1);
if (count.get(out) == 0) {
count.remove(out);
}
}
// 窗口合法时才能更新最长长度。
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func lengthOfLongestSubstringKDistinct(s string, k int) int {
if k == 0 {
return 0
}
count := make(map[byte]int)
left := 0
ans := 0
for right := 0; right < len(s); right++ {
count[s[right]]++
for len(count) > k {
out := s[left]
left++
count[out]--
if count[out] == 0 {
delete(count, out)
}
}
// 哈希表大小就是当前窗口不同字符数量。
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。左右指针各最多移动 $n$ 次，哈希表操作均摊为 $O(1)$。
- 空间复杂度：$O(k)$。哈希表在扩张瞬间最多保存 $k + 1$ 种字符，收缩结束后不超过 $k$ 种。
关键点总结
- 可变窗口的成立条件是「非法性单调」：区间越长字符种类越多，越界之后只能靠缩左端恢复，这决定了右端点无需回退。
- 计数减到 0 必须删键，这是
count.size()能代表不同字符数的前提，也是本题最容易漏的一行。- 更新答案的时机必须在收缩之后，保证参与取最大值的一定是合法窗口。
- 面试时要能解释两点：两层循环仍是 $O(n)$，因为左指针总共只移动 $n$ 次；若统计「恰好 $k$ 种」子数组，可用两次「至多」计数相减。
易错点总结
- 错误写法：收缩时只做
count.put(out, count.get(out) - 1)，却不在计数归零后count.remove(out)。用s = "eceba"、k = 2走：right = 3时表里有e、c、b三个键，收缩过程中它们的计数陆续减到 0 但键一直留着，count.size()永远是 3，退出条件永远不满足，left一路越过right，最终对还没进过窗口的字符做减一（Java 里count.get返回null触发空指针异常，Go 里left继续增长直到s[left]下标越界）。- 错误写法：把
ans = Math.max(ans, right - left + 1)放在收缩循环之前。用s = "eceba"、k = 2走：right = 3时窗口[0, 3]含e、c、b三种字符，却被当成合法窗口刷出长度 4，输出 4，而正确答案是 3。- 错误写法：收缩条件写成
while (count.size() >= k)。用s = "eceba"、k = 2走：窗口被压到最多只剩 1 种字符，而这个串里没有相邻重复字符，输出 1，正确答案是 3。- 错误写法：假设字符集是小写字母，用
int[] count = new int[26]加s.charAt(i) - 'a'索引。题目没有限定字符集，输入s = "Aa"时'A' - 'a'为负数，数组下标越界异常。- 错误写法：每次移动端点后重新截取子串并统计字符种类。虽然结果正确，但整体退化为 $O(n^2)$。
- 错误写法：把「子串」当成「子序列」，统计全局出现最多的 $k$ 种字符。该做法忽略连续性，例如
"abaccc"、k = 2的正确答案是"accc"的长度 4。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 3. 无重复字符的最长子串 | 中等 | 窗口内字符互不重复的特例 |
| 159. 至多包含两个不同字符的最长子串 | 中等 | 本题 k 固定为 2 的版本 |
| 904. 水果成篮 | 中等 | 同一模型换成数组与题面包装 |
| 992. K 个不同整数的子数组 | 困难 | 「恰好 k 种」拆成两次「至多」相减 |
| 76. 最小覆盖子串 | 困难 | 求最短合法窗口，收缩时机相反 |
| 424. 替换后的最长重复字符 | 中等 | 判非法条件依赖窗口内最高频字符 |