Shortest window covering at least k distinct symbols

Question

You have the sequence of symbols traded on a venue, one per tick. Find the length of the shortest contiguous stretch that contains at least k distinct symbols. If no such stretch exists, return $0$ .

symbols = ["A", "B", "A", "C", "B"], k = 3
-> 3            # the stretch A C B (or B A C) hits 3 distinct

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

Accepted Answer

This is the mirror image of the longest-window problem. Now the constraint (at least k distinct) gets easier as the window grows, so we grow until valid, then greedily shrink from left while still valid, recording every valid length. A hash map of counts tracks how many distinct symbols the window holds. Tracing the example with k = 3: the window first reaches 3 distinct at A B A C (index 3), then shrinks. Dropping the leading A still leaves {B, A, C} (a second A remains), giving B A C of length 3; dropping B breaks validity, so we stop. Later B at index 4 re-forms 3 distinct as A C B, also l…

Shortest window covering at least k distinct symbols

Your answer

More Coding questions