Count contiguous stretches with exactly k distinct symbols

Question

You have the sequence of symbols traded on a venue, one per tick. Count how many contiguous windows contain exactly k distinct symbols. Return the count. Aim for O(n).

Accepted Answer

The trick is exactly(k) = atMost(k) - atMost(k - 1). Counting windows with at most k distinct is easy with a sliding window: for each right endpoint, once the window is trimmed to at most k distinct, every window ending there and starting anywhere in [left, right] is valid, which adds right - left + 1 to the total. Tracing the example with k = 2: atmost(2) counts 8 windows (all except the two single-symbol-repeat cases push it up: totals 1, 2, 3, 2 across the four endpoints sum to 8), and atmost(1) counts 4. So exactlyk(2) = 8 - 4 = 4, matching the four listed windows. Each atmost call is O(n…

Count contiguous stretches with exactly k distinct symbols

Your answer

More Coding questions