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

2025/4/24 0:57:42 来源：https://blog.csdn.net/qq_40263592/article/details/147376976 浏览: 次关键词：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[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 0char_count = {}left = max_len = 0for right, char in enumerate(s):char_count[char] = char_count.get(char, 0) + 1while len(char_count) > 2:left_char = s[left]char_count[left_char] -= 1if char_count[left_char] == 0:del char_count[left_char]left += 1max_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;}
};