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 由英笔墨母组成
解题思路
方法：滑动窗口
利用滑动窗口和哈希表来维护差别字符的计数。
关键点：
[*]利用哈希表记载窗口内字符的出现次数
[*]当差别字符数凌驾2时，移动左指针
[*]更新最大长度
[*]处理惩罚边界情况
时间复杂度：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;
if (!dict.ContainsKey(c)) {
dict = 0;
}
dict++;
while (dict.Count > 2) {
char leftChar = s;
dict--;
if (dict == 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_count.get(char, 0) + 1
while len(char_count) > 2:
left_char = s
char_count -= 1
if char_count == 0:
del char_count
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]++;
while (charCount.size() > 2) {
charCount]--;
if (charCount] == 0) {
charCount.erase(s);
}
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};
性能分析
各语言实现的性能对比：
实现语言实行用时内存消耗特点C#92 ms38.2 MB实现简洁，性能适中Python156 ms16.8 MB代码最简洁C++24 ms9.6 MB性能最优 增补阐明
代码亮点
[*]利用滑动窗口优化时间复杂度
[*]利用哈希表维护字符计数
[*]代码结构清楚，易于维护
常见错误
[*]没有处理惩罚空字符串的情况
[*]没有正确处理惩罚字符计数为0的情况
[*]边界条件处理惩罚不当
相关题目
[*]3. 无重复字符的最长子串
[*]340. 至多包罗 K 个差别字符的最长子串
[*]424. 更换后的最长重复字符
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]