Longest Substring with At Most Two Distinct Characters

题目描述

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.

解题方法

也是hashtable + two pointer，这一题其实是follow up的特殊情况，应该是 with at most k characters， 那么我们可以用一个variable来记录出现过的 distinct characters的数量就可以了。

在遍历过程中的情况分类

• 遇到出现过的重复元素（在hashtable里），并且出现次数不为1（说明并没有被删掉），那么就加occurance
• 没有出现过，但是num of distinct chars还< k，就加入
• 否则就停止right pointer继续前进，可以推进左边界并且删掉开头的元素了

Solution

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        left = 0
        right = 0
        numDis = 0
        result = 0
        cDic = {}

        for left in range(len(s)):
            while right < len(s):
                cur = s[right]
                if cur in cDic and cDic[cur] != 0:
                    # if it's not a new distinct one, increment occurance
                    cDic[cur] += 1
                    result = max(result, right - left + 1)
                    right += 1
                elif numDis < 2:
                    # if num of distinct is still less than k, add into map
                    numDis += 1
                    cDic[cur] = 1
                    result = max(result, right - left + 1)
                    right += 1
                else:
                    break

            # remove left char occurance with for loop incrementing
            if s[left] in cDic:
                cDic[s[left]] -= 1
                if cDic[s[left]] == 0:
                    numDis -= 1

        return result

Reference

• program creek