Longest Substring with At Most K Distinct Characters

Problem

Given a string s and an integer k, return the length of the longest contiguous substring that contains no more than k different characters. If k is 0, the answer is 0.

• s has between 1 and 50,000 characters, drawn from printable ASCII.
• k is between 0 and 60.

Examples

• s = "pqpqrps", k = 2 → 4. "pqpq" uses only p and q; the r that follows would be a third character.
• s = "zz", k = 1 → 2. A single distinct character throughout.
• s = "mnomno", k = 0 → 0. No characters are allowed at all.

Hints

1. When a window first holds k + 1 different characters, which characters could you drop from the left to get back to k, and how far would that take the left edge?
2. Keep a count of each character currently inside a window, and note that "how many distinct characters" is just the number of keys with a positive count.
3. Variable-size sliding window: extend hi, and while the map has more than k keys, remove s[lo] and delete keys whose count reaches zero.