Longest window with at most k distinct symbols

Question

You have the sequence of symbols traded on a venue, one per tick. Find the length of the longest contiguous stretch containing at most k distinct symbols.

symbols = ["A", "A", "B", "A", "C", "C", "B"], k = 2
-> 4            # the stretch A A B A uses only {A, B}

Return the maximum window length. Aim for $O(n)$ .

Accepted Answer

Use a variable-size sliding window with a hash map of symbol counts inside the window. Extend right one tick at a time; whenever the map holds more than k distinct symbols, shrink from left until it doesn't. The key monotonicity: adding elements never removes a violation, so once invalid you must shrink, and each index enters and leaves the window at most once, giving a linear bound. Tracing the example: the window grows to A A B A (length 4, two distinct). Adding C makes three distinct, so the left edge slides forward to A C territory; no later window beats 4. Time O(n), the while loop advan…

Longest window with at most k distinct symbols

Your answer

More Coding questions