Longest Substring with At Most K Distinct Characters

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

sliding-window strings hash-map

Write a function `longest_substring_with_k_distinct(s: str, k: int) -> int` that returns the length of the longest contiguous substring of `s` that contains at most `k` distinct characters. A substring is a contiguous sequence of characters within the string. If `k` is 0, the result is 0. The input string may contain any printable ASCII characters, including spaces. The function should handle empty strings and cases where `k` is larger than the number of distinct characters in `s` (then the whole string is the answer). The algorithm should run in O(n) time and O(k) space using a sliding window with a dictionary.

Constraints

0 <= |s| <= 100000; 0 <= k <= 100000. The input string consists of printable ASCII characters. Time complexity should be O(n) where n is the length of the string. Space complexity O(k).

Example

>>> longest_substring_with_k_distinct('eceba', 2)
3
>>> longest_substring_with_k_distinct('aa', 1)
2
>>> longest_substring_with_k_distinct('aaaa', 2)
4
>>> longest_substring_with_k_distinct('abcabc', 3)
6
>>> longest_substring_with_k_distinct('abc', 2)
2
>>> longest_substring_with_k_distinct('', 2)
0
>>> longest_substring_with_k_distinct('a', 0)
0
>>> longest_substring_with_k_distinct('a', 1)
1

25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a sliding window with two pointers (left and right). Expand right, and when the window has more than k distinct characters, move left until it is valid again.

Keep a dictionary counting characters in the current window. The number of distinct characters is the number of keys.

Track the maximum window length seen while the window is valid.

When moving the left pointer, decrement the count of the character; if it becomes zero, remove it from the dictionary.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.