LeetCode 340. 至多包含 K 个不同字符的最长子串

2026-05-14 HGNULB 约 5 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决已掌握会员题 10-20 腾讯字节猿辅导

题目描述

✅ 340. 至多包含 K 个不同字符的最长子串

给定一个字符串 s 和一个整数 k，返回其中至多包含 k 种不同字符的最长子串的长度。

示例 1：

输入：s = "eceba", k = 2
输出：3
解释：最长子串是 "ece"，长度为 3。

示例 2：

输入：s = "aa", k = 1
输出：2
解释：整个字符串 "aa" 只包含一种字符，长度为 2。

提示：

1 <= s.length <= 10^5
0 <= k <= 50
s 由英文字母组成。

题意分析

给定字符串 s 和整数 k，寻找其中至多包含 k 种不同字符的最长连续子串，返回长度。限制的是字符种类，而不是字符总数：同一种字符可以重复出现多次，只占一种。子串必须连续，不能从不同位置挑出字符拼接。

字符串由英文字母组成，大小写按不同字符统计。k = 0 时不允许任何字符，答案为零；恰好有 k 种字符的子串仍然合法。

解法：滑动窗口维护字符种类

核心思路

[!blue]

用闭区间 [left, right] 表示当前窗口。右端每次加入一个字符，记录窗口内每种字符的出现次数。频次表只保存次数大于零的字符，因此表中键的数量就等于窗口的字符种类数。

若加入字符后种类数超过 k，就从左端依次移出字符。移出一次只减少对应频次，未必让种类数减少；只有某种字符的最后一次出现离开窗口，才能删除这个键。持续收缩到表大小不超过 k，窗口才重新合法。

为什么可以一直向右移动而不回退？某个左端因为种类太多被排除后，右端继续扩大只会增加或保持字符种类，它不可能重新变成合法起点。因此已经排除的左端不用再考虑。收缩也只在必要时进行，第一次恢复合法就停止，得到当前右端所能对应的最长合法子串。

在恢复合法之后，用 right - left + 1 更新答案。每一个可能的结束位置都被处理，而该结束位置的最长合法窗口也被考虑，所以最终最大值就是全局答案。使用频次而不是集合，是为了区分移出一个字符和移出该字符的最后一次出现。

解题步骤

若 k == 0，直接返回零；否则初始化频次表、左端和答案。

枚举右端 right，把新字符的频次加一。

当表中键数大于 k 时，减少 s[left] 的频次并推进左端；频次降为零就删除该键。

窗口合法后，使用 right - left + 1 更新最大长度。

扫描结束后返回答案。

代码实现

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)$。左右指针各最多走过字符串一次，每次进出窗口只需常量次哈希表操作。

空间复杂度：$O(\min(n, k + 1))$。窗口合法时最多有 k 种字符，加入一个新字符后最多暂时增加到 k + 1 种；也不会超过整个字符串的字符数。

关键点总结

[!green]

哈希表存每种字符的频次，表大小才代表种类数；频次之和对应的是窗口总长度。

超额窗口无法靠继续扩大变合法，因此必须移动左端，且左端无需回退。

频次降为零时删键，才能保证合法性判断与窗口实际内容一致。

易错点总结

[!yellow]

计数已经归零却不删除键，表大小不会正确减少，收缩甚至可能越过字符串边界。

每移出一个字符就直接删键，会忽略窗口内该字符的其他出现，低估实际种类数。

收缩条件使用 >= k，会排除恰好含有 k 种字符的合法窗口，应使用 > k。

收缩前就更新答案，会把超出种类限制的窗口算作可行结果。

按全局频次挑选字符无法保证连续性，题目要求的是原串中的连续区间。

相似题目

题目	难度	关联与区别
159. 至多包含两个不同字符的最长子串	中等	本题把不同字符种类上限从2推广到k，窗口频次归零时减少种类数的逻辑相同。
904. 水果成篮	中等	水果种类作为数组元素后，最多两种水果的连续区间就是k=2的同类窗口问题。
3. 无重复字符的最长子串	中等	用滑动窗口维护字符频次和有效左边界；本题允许最多 k 种字符，该题每个字符最多保留一次。
1100. 长度为 K 的无重复字符子串	中等	用滑动窗口维护字符频次和有效左边界；本题允许最多 k 种字符，该题固定窗口长度后统计无重复窗口。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/42200922

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！