Longest Substring with At Most K Distinct Characters

length_of_longest_substring_k_distinct.py

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

Examples:
Input: s = "eceba", k = 2
Output: 3 -- 'ece' is the longest

Input: s = "aa", k = 1
Output: 2 -- 'aa' is the longest
"""

def lengthOfLongestSubstringKDistinct(s, k):
    """
    :type s: str
    :type k: int
    :rtype: int
    """
    ret, left = 0, 0
    lastIndex = {}
    for i, char in enumerate(s):
        lastIndex[char] = i
        if len(lastIndex) > k:
            left = min(lastIndex.values())
            del lastIndex[s[left]]
            left += 1
        if i - left + 1 > ret:
            ret = i - left + 1
    return ret