340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

Solution: HashMap

import collections


class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_len = 0
        low = 0
        distinct = collections.defaultdict(int)
        for idx, char in enumerate(s):
            distinct[char] += 1
            while len(distinct) > k:
                first = s[low]
                distinct[first] -= 1
                if distinct[first] == 0:
                    del distinct[first]
                low += 1
            max_len = max(max_len, idx - low + 1)
        return max_len

Lessons:

• Use hash table to remember how many distinct characters are in current subarray.
• Once size of distinct is over the limit, use while loop to remove the leftmost characters and shrink size by one.
• Use two pointers to remember the maximum size during traverse.

Related:

• 76. Minimum Window Substring