340 Longest Substring with At Most K Distinct Characters

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

思路：典型的滑动窗口，双指针的问题。如果外面直接套while，太容易写错了。所以直接for loop j。然后移动i来确保每次都是valid的。用res来存最大的结果就行了。

import collections
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, j-i+1)
        return res


s = 'ab'
k = 1
so = Solution()
a = so.lengthOfLongestSubstringKDistinct(s, k)
print a

另外一种写法

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        d = {}
        low, res = 0, 0
        for i,c in enumerate(s):
            d[c] = i

            # delete a element from the dict and reset the window
            if len(d)>k:
                index = min(d.values())
                low = index + 1
                del d[s[index]]
            res = max(res, i-low+1)
        return res