Longest Substring with At Most K Distinct Characters

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

Input / Output

• Input: string s, int k.
• Output: max length.

Constraints

• |s| up to 10^5; O(n) expected.

Example

• s = "eceba", k = 2 → 3 ("ece"); s = "aa", k = 1 → 2.

Expected approach

• Sliding window with a char → count map: extend right; while the map holds k+1 distinct keys, shrink from the left (decrement, remove at zero). Track max window length on every valid state. O(n) time, O(k) space. Variants to know: exactly-k (atMost(k) − atMost(k−1)), k = 2 (fruit basket), and the at-most-one-odd/others family — same skeleton.