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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 计数（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口 + 计数（推荐）

核心思路：

使用双指针维护窗口 [left, right]。

哈希表统计窗口内字符出现次数，distinct 表示不同字符数。

当 distinct > k 时左指针收缩，直到满足条件。

每次更新最大长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(k)，窗口内最多 k 种字符。

// 滑动窗口统计不同字符数
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s == null || s.isEmpty()) {
            return 0;
        }

        Map<Character, Integer> count = new HashMap<>();
        int left = 0;
        int distinct = 0;
        int res = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            count.put(c, count.getOrDefault(c, 0) + 1);
            if (count.get(c) == 1) {
                distinct++;
            }

            while (distinct > k) {
                char lc = s.charAt(left++);
                count.put(lc, count.get(lc) - 1);
                if (count.get(lc) == 0) {
                    distinct--;
                }
            }

            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}

// 滑动窗口统计不同字符数
func lengthOfLongestSubstringKDistinct(s string, k int) int {
	if k == 0 || len(s) == 0 {
		return 0
	}

	count := make(map[byte]int)
	left := 0
	distinct := 0
	res := 0

	for right := 0; right < len(s); right++ {
		c := s[right]
		count[c]++
		if count[c] == 1 {
			distinct++
		}

		for distinct > k {
			lc := s[left]
			left++
			count[lc]--
			if count[lc] == 0 {
				distinct--
			}
		}

		if right-left+1 > res {
			res = right - left + 1
		}
	}

	return res
}

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	滑动窗口
76. 最小覆盖子串	困难	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口
424. 替换后的最长重复字符	中等	滑动窗口
904. 水果成篮	中等	滑动窗口
1695. 删除子数组的最大得分	中等	滑动窗口

本文作者: HGNULB

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