159. Longest-Substring-with-At-Most-Two-Distinct-Characters.md

Description

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

---

看到这题，第一感觉就是使用groupby来做, 因为它将字母都按组分好了：

from itertools import groupby


class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(set(s)) == 1 or not s: return len(s)

        res = 0
        gb = []
        for i in groupby(s):
            gb.append([i[0], len(list(i[1]))])
        length = len(gb)

        for i, v in enumerate(gb):
            if i < length - 2:
                curCnt = v[1] + gb[i + 1][1]
                for k in range(i + 2, length):
                    if gb[k][0] == gb[i][0] or gb[k][0] == gb[i + 1][0]:
                        curCnt += gb[k][1]
                    else:
                        break
                res = max(res, curCnt)

            elif i == length - 2:
                res = max(res, v[1] + gb[i + 1][1])
        return res

但是由于时间复杂度大于O(n),通过不了(126/127).....

python solution

后来看别人代码，是用滑动窗口来解的，思路真的巧妙:

• 维护一个从左到右的滑动窗口。如果遇到第三个字符，那么将第一个位置的字符移出去。
• 这种解法适用于k distinct characters

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 从字典中移除掉位置在最前面的元素。
        def remove_lowest_char(distinct):
            lowest_pos = min(distinct.values())
            for k, v in distinct.items():
                if v == lowest_pos:
                    char = k
            distinct.pop(char)

        distinct = {}  # char=>position
        maxLen = 0
        left = 0

        for right, char in enumerate(s):
            if len(distinct) == 2 and char not in distinct:
                left = min(distinct.values()) + 1 # 因为字典中存储的是元素的“最新”位置，所以只需要将left向前移一位。
                remove_lowest_char(distinct)
            distinct[char] = right   # 永远保证字典中存储的是元素的“最新”位置。
            maxLen = max(maxLen, right - left + 1)
        return maxLen


print(Solution().lengthOfLongestSubstringTwoDistinct("aabbaaabbbaaaddaa"))