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.

Ideas:

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 is 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.

Solution:

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, res = 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
        res = max(i - low +1, res)
    return res