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

Enumerating all ranges with a fresh Set can cost O(n³); retaining counts separately for each start reduces that baseline to O(n²). The final algorithm reuses one moving window.

Moving the boundary instead of restarting

Grow the right boundary, then shrink from the left until the distinct-label count is valid again. A frequency map is necessary because removing one of two a labels leaves a still present. Delete a key only when its count reaches zero; otherwise Map.size no longer means the number of kinds in the window.

For ["a", "b", "a", "c", "b"] with k=2, the first three labels form a valid length-three window. Adding c requires removing both the first a and then b before only two kinds remain. A single left shift would be insufficient. Measure the answer only after restoring validity.

A discarded start cannot become valid at a later right endpoint: extending a range cannot reduce its distinct count. This monotonic argument justifies never moving the left boundary backward. Exact string equality is the only label policy; case and empty labels are not normalized.

const counts = new Map([["a", 2], ["b", 1]]);
counts.set("a", counts.get("a") - 1);
console.log(counts.get("a"), counts.size); // 1 2: one a still remains
counts.delete("b");
console.log(counts.size); // 1

Knowing when a window is valid

Each boundary advances at most n times, giving expected O(n) time with map operations and O(k+1) active frequency entries during restoration, excluding input/output representation. Use this when extending a range can only worsen the constraint. Some range properties are not monotone, so a moving window is not a universal replacement for range enumeration.

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