Longest Substring with At Most K Distinct Characters

Problem: Longest Substring with At Most K Distinct Characters

We can use a hash table to store the occurence of letters in the current longest substring with at most k distinct characters while reading through the string. If the size of the table get bigger than k, we need to remove characters from the head of the current substring and update the hash table until its size goes back to k.

Code in Python:

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
    """
    :type s: str
    :type k: int
    :rtype: int
    """
    if k == 0: return 0
    m = {}
    res, cur = 0, ""
    for c in s:
        if c in m:
            m[c] += 1
            cur += c
        else:
            if len(m) >= k:
                if len(cur) > res: res = len(cur)
                while len(m) >= k:
                    if m[cur[0]] <= 1: del m[cur[0]]
                    else: m[cur[0]] -= 1
            cur = cur[1:]
            m[c] = 1
            cur += c
    return max(res, len(cur))