Longest Substring with At Most K Distinct Characters

The general idea is to iterate over string s.

Using sliding window and hash table and add character one by one

• If length of hash table is less or equal to k, we record the substring length.
• If length of has table is greater than k, we remove the lowest index of character from table.

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if s == "":
            return 0

        hash_table = {}
        start = 0
        maximum = 0

        for i, c in enumerate(s):
            hash_table[c] = i
            if len(hash_table) > k:
                tmp = min(hash_table.values())
                hash_table.pop(s[tmp])
                start = tmp+1

            maximum = max(i-start+1, maximum)
        return maximum