leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法

迷南。 2022-05-26 10:16 138阅读 0赞

*  题目解析
 *  代码如下

# 题目解析 #

这一题是一道会员的题目，题目介绍如下：

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
    
    For example, Given s = “eceba”,
    
    T is "ece" which its length is 3.

**意思的大概情况是找出一个字符串中不相同字符不超过两个的最长子串**

根据我们之前介绍的滑动窗口法的解法:  
[滑动窗口法详解][Link 1]  
[leetcode 438. Find All Anagrams in a String 滑动窗口法][leetcode 438. Find All Anagrams in a String]  
[leetcode 3. Longest Substring Without Repeating Characters 最长非重复子串的长度 滑动窗口法][leetcode 3. Longest Substring Without Repeating Characters _]

此题与leetcode第三题，相似非常高，可以先做第三题再做这一题：

# 代码如下 #

from collections import defaultdict
    
    class Solution:
        def lengthOfLongestSubstringTwoDistinct(self, s):
            begin, end, counter, length = 0, 0, 0, 0
            map_dict = defaultdict(int)
            while end < len(s):
                c = s[end]
                map_dict[c] += 1
                # counter 表示新的字符
                if map_dict == 1:
                    counter += 1
                end += 1
                # 如果新字符的数量大于2,就开始移动窗口
                while counter > 2:
                    char_tmp = s[begin]
                    if map_dict[char_tmp] == 1:
                        counter -= 1
                    map_dict[char_tmp] -= 1
                    begin += 1
                length = max(length, end - begin)
            return length

[Link 1]: https://blog.csdn.net/sty945/article/details/79846516
[leetcode 438. Find All Anagrams in a String]: https://blog.csdn.net/sty945/article/details/80103668
[leetcode 3. Longest Substring Without Repeating Characters _]: https://blog.csdn.net/sty945/article/details/80142835