Sum

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

Example 1:

Input: 
s = "eceba", k = 2
Output: 
3
Explanation: 
T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 
2

Explanation: 
T is "aa" which its length is 2.

Thoughts:

1. d: a hash table to record distinct value (through (len(d)).

2. every iteration compare (i - low + 1) with max value (returned value in the end)

   1. when d is over k, delete the least value entry, set low = min(d.values()) + 1

Code:

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        d, low, ans = {}, 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
            ans = max(i - low + 1, ans)
        return ans