LeetCode第159题_至多包含两个不同字符的最长子串

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; }};

性能分析

各语言实现的性能对比：

补充说明

代码亮点

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

常见错误

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

相关题目

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