159.Longest Substring with At Most Two Distinct Characters

Tags: [string], [two_pointer], [map]

Com: {g}

Link: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/\#/description

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.

Solution: Map

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

        size = len(s)
        char_counts = collections.defaultdict(int)
        max_len = 0

        start = 0
        end = 0
        while end < size:
            char_counts[s[end]] += 1
            if len(char_counts) > 2:
                sub_len = end - start
                max_len = max(max_len, sub_len)

                # shrink window
                while start < end and len(char_counts) > 2:
                    char_counts[s[start]] -= 1
                    if char_counts[s[start]] == 0:
                        del char_counts[s[start]]

                    start += 1

            end += 1

        sub_len = end - start
        max_len = max(max_len, sub_len)
        return max_len

Revelation:

• In Python, collections.defaultdict(int) will create a dict, the key's default value is integer 0.

Note:

• Time complexity = O(n), n is the length of the given string.