Description:

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

Example 1:

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"

Challenge

O(n) time

Solution:

from collections import defaultdict
class Solution:
    """
    @param s: A string
    @param k: An integer
    @return: An integer
    """
    def lengthOfLongestSubstringKDistinct(self, string, k):
        # write your code here
        dic = defaultdict(int)
        length = 0
        ret = 0
        
        for i,s in enumerate(string):
            dic[s] += 1
            length += 1
            while len(dic.keys()) > k:
                cache = string[i-length+1]
                dic[cache] -= 1
                if dic[cache] == 0:
                    dic.pop(cache)
                length -= 1
            ret = max(ret,length)
            
        return ret

Total runtime 1157 ms
Your submission beats 26.40% Submissions!