LeetCode 159 至多包含两个不同字符的最长子串：滑动窗口经典题

题目描述

给定一个字符串 s，找出 至多 包含两个不同字符的最长子串 t，并返回该子串的长度。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入: s = "eceba"
输出: 3
解释: t 是 "ece"，长度为3。

示例 2：

输入: s = "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。

示例 3：

输入: s = "aaaaa"
输出: 5
解释: t 是 "aaaaa"，长度为5。

提示

• 1 <= s.length <= 105
• s 由英文字母组成

解题思路

方法：滑动窗口

使用滑动窗口和哈希表来维护不同字符的计数。 关键点：

1. 使用哈希表记录窗口内字符的出现次数
2. 当不同字符数超过2时，移动左指针
3. 更新最大长度
4. 处理边界情况

时间复杂度：O(n)，其中n是字符串长度。 空间复杂度：O(1)，因为最多存储3个字符的计数。

代码实现

C# 实现

public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        if (string.IsNullOrEmpty(s)) return 0;
        
        Dictionary<char, int> dict = new Dictionary<char, int>();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.Length; right++) {
            char c = s[right];
            if (!dict.ContainsKey(c)) {
                dict[c] = 0;
            }
            dict[c]++;
            
            while (dict.Count > 2) {
                char leftChar = s[left];
                dict[leftChar]--;
                if (dict[leftChar] == 0) {
                    dict.Remove(leftChar);
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

Python 实现

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        if not s:
            return 0
            
        char_count = {}
        left = max_len = 0
        
        for right, char in enumerate(s):
            char_count[char] = char_count.get(char, 0) + 1
            
            while len(char_count) > 2:
                left_char = s[left]
                char_count[left_char] -= 1
                if char_count[left_char] == 0:
                    del char_count[left_char]
                left += 1
                
            max_len = max(max_len, right - left + 1)
            
        return max_len

C++ 实现

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        if (s.empty()) return 0;
        
        unordered_map<char, int> charCount;
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            charCount[s[right]]++;
            
            while (charCount.size() > 2) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	实现简洁，性能适中
Python	156 ms	16.8 MB	代码最简洁
C++	24 ms	9.6 MB	性能最优

补充说明

代码亮点

1. 使用滑动窗口优化时间复杂度
2. 使用哈希表维护字符计数
3. 代码结构清晰，易于维护

常见错误

1. 没有处理空字符串的情况
2. 没有正确处理字符计数为0的情况
3. 边界条件处理不当

相关题目

• 3. 无重复字符的最长子串
• 340. 至多包含 K 个不同字符的最长子串
• 424. 替换后的最长重复字符

讨论

有几个问题可以思考一下：

1. 滑动窗口什么时候需要收缩（左指针右移）？判断条件是什么？
2. 如果改成“至多包含K个不同字符”，代码需要改哪里？
3. 滑动窗口这个技巧还能用来解决哪些问题？

欢迎在评论区讨论。

---

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。