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

Maintain the distinct-value constraint with frequencies. Removing one a from a window containing two occurrences does not remove a from its distinct set. Delete a counter only after it reaches zero. After adding a rightmost value, move the left boundary in a loop until validity returns; moving left once may leave three kinds in a two-kind window.

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.

std::map<std::string,Int> counts{{"a",2},{"b",1}};
if (--counts["a"] == 0) counts.erase("a"); // a still remains here

Knowing when a window is valid

A discarded start never becomes useful for a later endpoint, because extending a window cannot reduce its distinct count. That monotonic argument permits both boundaries to move forward only, giving expected O(n) work with a hash map. Measure the answer after shrinking. A zero limit is valid and allows only an empty window; a negative limit is a distinct invalid-input case. String labels are compared exactly, including empty strings and case.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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