Longest Substring With At Most K Distinct Characters

Description

Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters.

Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The longest substring with at most 2 distinct characters is "ece" (length 3). It contains only 'e' and 'c'.

Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The entire string "aa" has only 1 distinct character, which is <= 1.

Example 3:
Input: s = "aabbcc", k = 2
Output: 4
Explanation: The longest substring with at most 2 distinct characters is "aabb" or "bbcc" (both length 4).

Constraints

1 <= s.length <= 5 * 10^4
0 <= k <= 50
s consists of lowercase English letters

Signature

def solution(s: str, k: int) -> int: ...

Complexity

Time: O(n)
Space: O(k)

Hints

Pattern: Sliding window with hash map
Approach: Expand right pointer, when distinct chars > k, shrink left pointer until valid. Track max length.
Complexity: Maintain a window with at most k distinct chars using a frequency map

Solutions

Python

def solution(s: str, k: int) -> int:
    m = {}
    left = 0
    result = 0
    for right in range(len(s)):
        a = s[right]

        if a not in m:
            m[a] = 0
        m[a] += 1

        while len(m) > k:
            m[s[left]] -= 1
            if m[s[left]] == 0:
                del m[s[left]]
            left += 1
        result = max(result, sum(m.values()))

    return result