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!
