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.

# Hide Company Tags Google

# Hide Tags Hash Table Two Pointers String

# Hide Similar Problems (M) Longest Substring Without Repeating Characters (H) Sliding Window Maximum (H) Longest Substring with At Most K Distinct Characters

class Solution(object):

    def lengthOfLongestSubstringTwoDistinct(self, s):

        """

        :type s: str

        :rtype: int

        """

        char1, right1, char2, right2 = '', 0, '', 0

        start = 0

        longest = 0

        for i, c in enumerate(s):

            if not char1 or char1==c:

                char1=c

                right1=i

            elif not char2 or char2==c:

                char2=c

                right2=i

            else:

                # print i

                if right1<right2:

                    char1 = c

                    start=right1+1

                    right1 = i

                else:

                    char2 = c

                    start=right2+1

                    right2 = i

            #print 'i={},start={},right1={},righ2={}'.format(i,start,right1,right2)

            longest = max(longest, i-start+1)

        return longest

sol = Solution()

assert sol.lengthOfLongestSubstringTwoDistinct("cdaba")==3