340.Longest Substring with At Most K Distinct Characters

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

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

T is "ece" which its length is 3.

Method 1 Dictionary. O(n) time, O(n) space

• Loop thorugh the string, store the most recent index of each character in the map.
• Maintain a last variable that starts at 0, indicating the start of the substring.
• Once map has size > k, find the key with smallest value, that should be the first character of the substring. Remove it from the map, increment the last variable by 1.
• Compare the max length with the current index - current last to find the max length.

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        res, hm = 0, {}
        last = 0
        for i, c in enumerate(s):
            hm[c] = i
            if len(hm) > k:
                last = min(hm.values())
                del hm[s[last]]
                last += 1
            res = max(res, i - last + 1)
        return res