LeetCode第159题_至多包罗两个差别字符的最长子串

LeetCode 第159题：至多包罗两个差别字符的最长子串

题目形貌

给定一个字符串 s，找出 至多 包罗两个差别字符的最长子串 t，并返回该子串的长度。
难度

中等
题目链接

点击在LeetCode中检察题目
示例

示例 1：

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

复制代码

示例 2：

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

复制代码

示例 3：

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

复制代码

提示

• 1 <= s.length <= 105
  
• s 由英笔墨母组成
  

解题思路

方法：滑动窗口

利用滑动窗口和哈希表来维护差别字符的计数。
关键点：

• 利用哈希表记载窗口内字符的出现次数
  
• 当差别字符数凌驾2时，移动左指针
  
• 更新最大长度
  
• 处理惩罚边界情况
  

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

C# 实现

1. public class Solution {
2.     public int LengthOfLongestSubstringTwoDistinct(string s) {
3.         if (string.IsNullOrEmpty(s)) return 0;
4.         
5.         Dictionary<char, int> dict = new Dictionary<char, int>();
6.         int left = 0, maxLen = 0;
7.         
8.         for (int right = 0; right < s.Length; right++) {
9.             char c = s[right];
10.             if (!dict.ContainsKey(c)) {
11.                 dict[c] = 0;
12.             }
13.             dict[c]++;
14.             
15.             while (dict.Count > 2) {
16.                 char leftChar = s[left];
17.                 dict[leftChar]--;
18.                 if (dict[leftChar] == 0) {
19.                     dict.Remove(leftChar);
20.                 }
21.                 left++;
22.             }
23.             
24.             maxLen = Math.Max(maxLen, right - left + 1);
25.         }
26.         
27.         return maxLen;
28.     }
29. }

复制代码

Python 实现

1. class Solution:
2.     def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
3.         if not s:
4.             return 0
5.             
6.         char_count = {}
7.         left = max_len = 0
8.         
9.         for right, char in enumerate(s):
10.             char_count[char] = char_count.get(char, 0) + 1
11.             
12.             while len(char_count) > 2:
13.                 left_char = s[left]
14.                 char_count[left_char] -= 1
15.                 if char_count[left_char] == 0:
16.                     del char_count[left_char]
17.                 left += 1
18.                
19.             max_len = max(max_len, right - left + 1)
20.             
21.         return max_len

复制代码

C++ 实现

1. class Solution {
2. public:
3.     int lengthOfLongestSubstringTwoDistinct(string s) {
4.         if (s.empty()) return 0;
5.         
6.         unordered_map<char, int> charCount;
7.         int left = 0, maxLen = 0;
8.         
9.         for (int right = 0; right < s.length(); right++) {
10.             charCount[s[right]]++;
11.             
12.             while (charCount.size() > 2) {
13.                 charCount[s[left]]--;
14.                 if (charCount[s[left]] == 0) {
15.                     charCount.erase(s[left]);
16.                 }
17.                 left++;
18.             }
19.             
20.             maxLen = max(maxLen, right - left + 1);
21.         }
22.         
23.         return maxLen;
24.     }
25. };

复制代码

性能分析

各语言实现的性能对比：
实现语言实行用时内存消耗特点C#92 ms38.2 MB实现简洁，性能适中Python156 ms16.8 MB代码最简洁C++24 ms9.6 MB性能最优 增补阐明

代码亮点

• 利用滑动窗口优化时间复杂度
  
• 利用哈希表维护字符计数
  
• 代码结构清楚，易于维护
  

常见错误

• 没有处理惩罚空字符串的情况
  
• 没有正确处理惩罚字符计数为0的情况
  
• 边界条件处理惩罚不当
  

相关题目

• 3. 无重复字符的最长子串
  
• 340. 至多包罗 K 个差别字符的最长子串
  
• 424. 更换后的最长重复字符
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。