Medium

Longest Substring with At Most K Distinct Characters

LAB

Return the length of the longest substring containing at most k distinct characters.

EXAMPLES

Example 1

Input
{
  "s": "eceba",
  "k": 2
}

Output
3

FUNCTION SHAPE

s: stringk: int→int

SOLUTION NOTE

This function is monotonic: TTTTTFFFF. Small strings are valid (have at most k distinct chars), large strings invalid.

Key points:
1. Max template
2. Counter()
3. Invalid condition: len(freq) > k
4. Res = max(res, r-l+1)

Reveal reference solution +

pythonREFERENCE

def lengthOfLongestSubstringKDistinct(self, s: str, k: int):
    n, l, freq, res = len(s), 0, Counter(), 0

    for r in range(n):
        freq[s[r]] += 1

        while len(freq) > k:
            freq[s[l]] -= 1
            if freq[s[l]] == 0: del freq[s[l]]
            l += 1

        res = max(res, r - l + 1)

    return res

TimeO(n)

SpaceO(k)

Open on LeetCode ↗