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

📖 文章摘要

本文详细解析LeetCode第340题“至多包含K个不同字符的最长子串”，这是一道中等难度的滑动窗口问题。文章提供了基于滑动窗口和哈希表的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理和滑动窗口算法能力的程序员。

核心知识点： 滑动窗口、哈希表、字符串处理
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升滑动窗口算法能力的程序员

题目描述

给定一个字符串 s 和一个整数 k ，请找出至多包含 k 个不同字符的最长子串，并返回该子串的长度。

示例

示例 1：

输入: s = "eceba", k = 2
输出: 3
解释: 子串 "ece" 包含 2 个不同的字符。

示例 2：

输入: s = "aa", k = 1
输出: 2
解释: 子串 "aa" 包含 1 个不同的字符。

提示

1 <= s.length <= 5 * 10^4
0 <= k <= 50
s 只包含小写英文字母

解题思路

方法：滑动窗口 + 哈希表

使用滑动窗口和哈希表来维护当前窗口中的字符及其出现次数。

关键点：

使用哈希表记录字符出现次数
使用滑动窗口维护符合条件的子串
动态更新最大长度
及时收缩窗口保持不同字符数量不超过k

具体步骤：

初始化左右指针和哈希表
右指针向右扩展窗口
当不同字符数超过k时，左指针收缩
更新最大长度
返回结果

时间复杂度：O(n)，其中n是字符串长度空间复杂度：O(k)，哈希表大小不超过k

图解思路

滑动窗口分析表

步骤	窗口内容	不同字符数	当前长度	最大长度
初始	e	1	1	1
扩展	ec	2	2	2
扩展	ece	2	3	3
扩展	eceb	3	4	3
收缩	ceb	3	3	3
收缩	eb	2	2	3
扩展	eba	3	3	3

哈希表状态分析

初始状态：{}
添加'e'：{'e': 1}
添加'c'：{'e': 1, 'c': 1}
添加'e'：{'e': 2, 'c': 1}
添加'b'：{'e': 2, 'c': 1, 'b': 1}
移除'e'：{'e': 1, 'c': 1, 'b': 1}
移除'c'：{'e': 1, 'b': 1}
添加'a'：{'e': 1, 'b': 1, 'a': 1}

代码实现

C# 实现

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        if (k == 0) return 0;
        
        var charCount = new Dictionary<char, int>();
        int maxLength = 0;
        int left = 0;
        
        for (int right = 0; right < s.Length; right++) {
            // 添加右边的字符
            if (!charCount.ContainsKey(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            // 收缩窗口
            while (charCount.Count > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
            
            // 更新最大长度
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Python 实现

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        
        char_count = {}
        max_length = 0
        left = 0
        
        for right in range(len(s)):
            # 添加右边的字符
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            
            # 收缩窗口
            while len(char_count) > k:
                char_count[s[left]] -= 1
                if char_count[s[left]] == 0:
                    del char_count[s[left]]
                left += 1
            
            # 更新最大长度
            max_length = max(max_length, right - left + 1)
        
        return max_length

C++ 实现

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if (k == 0) return 0;
        
        unordered_map<char, int> charCount;
        int maxLength = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {
            // 添加右边的字符
            charCount[s[right]]++;
            
            // 收缩窗口
            while (charCount.size() > k) {
                if (--charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            
            // 更新最大长度
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

执行结果

C# 实现

执行用时：76 ms
内存消耗：35.8 MB

Python 实现

执行用时：52 ms
内存消耗：15.2 MB

C++ 实现

执行用时：8 ms
内存消耗：7.8 MB

性能对比

语言	执行用时	内存消耗	特点
C#	76 ms	35.8 MB	代码结构清晰
Python	52 ms	15.2 MB	实现最简洁
C++	8 ms	7.8 MB	性能最优

代码亮点

🎯 高效的滑动窗口实现
💡 巧妙的哈希表应用
🔍 优雅的窗口收缩逻辑
🎨 清晰的代码结构

常见错误分析

🚫 忽略k=0的特殊情况
🚫 窗口收缩条件错误
🚫 字符计数更新不当
🚫 最大长度更新时机不对

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
滑动窗口	O(n)	O(k)	高效简洁	需要额外空间
暴力枚举	O(n^2)	O(k)	直观易懂	效率低下

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第340题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法：滑动窗口 + 哈希表

图解思路

滑动窗口分析表

哈希表状态分析

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流