class Solution(object):
"""
The general idea is to iterate over string s.
Always put the character c and its location i in the dictionary d.
1) If the sliding window contains less than or equal to k distinct characters, simply record the return value, and move on.
2) Otherwise, we need to remove a character from the sliding window.
Here's how to find the character to be removed:
Because the values in d represents the rightmost location of each character in the sliding window, in order to find the longest substring T, we need to locate the smallest location, and remove it from the dictionary, and then record the return value.
"""
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
# Use dictionary d to keep track of (character, location) pair,
# where location is the rightmost location that the character appears at
d = {}
low, ret = 0, 0
for i, c in enumerate(s):
d[c] = i
if len(d) > k:
low = min(d.values())
del d[s[low]]
low += 1
ret = max(i  low + 1, ret)
return ret
10line Python Solution using dictionary with easy to understand explanation



Share my Two pointer algorithm
class Solution(object): def lengthOfLongestSubstringKDistinct(self, s, k): d = collections.defaultdict(int) i, res = 0, 0 for j in range(len(s)): d[s[j]] += 1 # while have more than k, we keep removing from i while len(d)>k: d[s[i]] = 1 if d[s[i]] == 0: del d[s[i]] i += 1 res = max(res, ji+1) return res

The while is unnecessary in your algorithm. Since we are only moving by one each time, you can change it to an if.
@zqiu01 said in 10line Python Solution using dictionary with easy to understand explanation:
d = collections.defaultdict(int)
i, res = 0, 0
for j in range(len(s)):
d[s[j]] += 1
# while have more than k, we keep removing from i
while len(d)>k:
d[s[i]] = 1
if d[s[i]] == 0:
del d[s[i]]
i += 1
res = max(res, ji+1)
return res


@xiyayan @lucascho: I think the time complexity is O(n).
The dictionary will have at most 256 characters (or whatever the alphabet size used for constructing the string is  256 for an ascii string). Since there are a fixed number of characters therefore there are a fixed number of keyvalue pairs in the dictionary. And finding min with fixed number of characters will be 256 ops in the worst case which is as good as O(1). So, overall time complexity of this solution should be O(n) just due to the outermost loop.
