K Distinct Window

Problem

You receive a string s and an integer k. Return the length of the longest contiguous substring of s that contains at most k distinct characters.

I usually frame it as a log line: every character is an event type, and we want the longest stretch of the log that touches at most k different services.

Examples

Example 1, s = "aabacbebebe", k = 3 → 7 The window "cbebebe" holds {c, b, e} and has length 7. Extending it one step to the left pulls in a as a fourth type.

Example 2, s = "aaaa", k = 1 → 4 The whole string qualifies.

Edge, k = 0 → 0, and an empty string → 0.

Constraints

• 1 <= len(s) <= 10^5, lowercase ASCII.
• 0 <= k <= 26.
• Target O(n) time and O(k) extra space.

What they look for

Two pointers plus a frequency map, shrinking from the left only while the distinct count exceeds k. The common slip is decrementing a count and forgetting to delete the key when it hits zero, which makes the distinct count wrong. Expect a follow-up asking for the substring itself rather than its length, and a question about why the loop is still linear even though there is a nested while.