https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

340. Longest Substring with At Most K Distinct Characters.py

# Time: O(n)
# Space: O(1)
# 340. Longest Substring with At Most K Distinct Characters
'''
 01234
"eceba" k = 2
--------------
visited = {e:1,c:0,b:1}
01234
eceba
  i
   j
distinct_count = 2
longest = 3
'''
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        longest = 0
        i = 0
        visited = [0 for _ in xrange(256)]
        distinct_count = 0
        
        
        for j, char in enumerate(s):
            if visited[ord(char)] == 0:
                distinct_count += 1
            
            visited[ord(char)] += 1
            while distinct_count > k:
                visited[ord(s[i])] -= 1
                if visited[ord(s[i])] == 0:
                    distinct_count -= 1
                i += 1
            longest = max(longest, j - i + 1)
        return longest