Sliding windows with counts

A support engineer is looking through a session's service labels. She wants the longest uninterrupted stretch involving at most two different services, so she can isolate a smaller working set to investigate. Sorting would destroy the sequence, and allowing gaps would answer a different question.

Trying every start works, but each new attempt recounts much of the same stretch. A sliding window keeps the current counts and moves its boundaries only as far as necessary.

Finding a stretch with few services

A window maintains counts for exactly one contiguous range. When a new label breaches the distinct-value budget, advance the left boundary until valid again. Remove zero-count keys so map size still represents distinct values.

Moving the boundary instead of restarting

Read a, b, a, c, b with a two-service limit. The first three labels fit. Adding c creates three kinds: removing the first a is insufficient because another a remains. Remove b too and the window becomes a, c. Delete a label's map entry only when its final occurrence leaves; otherwise the number of keys no longer equals the number of active services.

counts := map[string]int{"api": 1}
counts["api"]--
if counts["api"] == 0 { delete(counts, "api") }

Knowing when a window is valid

Each boundary moves forward at most n times; the inner shrink loop therefore stays linear overall. Keeping a historical set rather than live counts fails when labels leave. This model suits bounded working sets and recent-event analysis, while noncontiguous selections need another algorithm.

Each position enters the window once and leaves at most once. Expected hash-map time is therefore O(n), even with the inner shrink loop. There are at most k+1 live kinds during expansion, bounded by the input itself. This proof needs a constraint that cannot repair an invalid start merely by extending the right boundary.

The support report needs an uninterrupted stretch; allowing gaps between matching labels would answer a different question.