Longest substring with at most k distinct characters

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

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_at_most_k(s: str, k: int) -> int — 0 when s is empty or k is 0.

Example

longest_at_most_k("eceba", 2)   ->  3     # "ece"
longest_at_most_k("aa", 1)      ->  2
longest_at_most_k("abaccc", 2)  ->  4     # "accc"
longest_at_most_k("abc", 0)     ->  0

Constraints

• 0 <= len(s) <= 2 * 10^5; 0 <= k <= len(s).
• s may hold any characters, not only lowercase letters.

Clarifying questions

• What should k = 0 return?
• Is the character set small (26 letters) or arbitrary Unicode?
• Do you want the length or the substring itself?

What a strong answer covers

• A sliding window with a count per character: extend the right end, and while the window holds more than k distinct characters, move the left end and drop counts that reach zero.
• O(n) time, since each index enters and leaves the window once; O(min(n, alphabet)) space.
• Edge cases: empty string, k = 0, k at least the number of distinct characters (the whole string).
• Tests with the examples and a string of one repeated character.

Follow-ups

• Return the substring, and the first one when several tie.
• The string arrives as a stream too large to hold: keep the last index of each character in an ordered map so the window shrinks in one step.
• Exactly k distinct characters, or count the substrings with at most k.