0159. 至多包含两个不同字符的最长子串

0159. 至多包含两个不同字符的最长子串 #

  • 标签:哈希表、双指针、字符串、滑动窗口
  • 难度:中等

题目大意 #

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

解题思路 #

使用滑动窗口来求解。

left,right 指向字符串开始位置。

不断向右移动 right 指针,使用 count 变量来统计滑动窗口中共有多少个字符,以及使用哈希表来统计当前字符的频数。

当滑动窗口的字符多于 2 个时,向右 移动 left 指针,并减少哈希表中对应原 left 指向字符的频数。

最后使用 max_count 来维护最长子串 t 的长度。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import collections
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        max_count = 0
        k = 2
        counts = collections.defaultdict(int)
        count = 0
        left, right = 0, 0
        while right < len(s):
            if counts[s[right]] == 0:
                count += 1
            counts[s[right]] += 1
            right += 1
            if count > k:
                if counts[s[left]] == 1:
                    count -= 1
                counts[s[left]] -= 1
                left += 1
            max_count = max(max_count, right - left)
        return max_count
本站总访问量  次  |  您是本站第  位访问者