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

This lesson asks for the longest range containing at most k distinct values. A frequency map is necessary: a set alone cannot tell whether removing one occurrence also removes that value's final occurrence from the window.

A fixed-start baseline can extend a count map until the first invalid endpoint:

values, k = ["a", "b", "a", "c", "b"], 2
counts = {}
for right, value in enumerate(values):
    counts[value] = counts.get(value, 0) + 1
    if len(counts) > k:
        break
print(right, counts)

It stops at index 3, with three distinct keys. Restarting this scan for each possible left boundary repeats work.

Moving the boundary instead of restarting

Take ['a', 'b', 'a', 'c', 'b'] with k=2. Use an inclusive right index in this trace:

When c enters, removing the first a leaves another a. The window still contains three kinds. Remove b next, delete its zero count, and validity returns. Moving left only once per violation would be incorrect.

The moving-window kernel keeps positive counts and measures only restored windows:

values, k = ["a", "b", "a", "c", "b"], 2
counts, left, best = {}, 0, 0
for right, value in enumerate(values):
    counts[value] = counts.get(value, 0) + 1
    while len(counts) > k:
        old = values[left]
        counts[old] -= 1
        if counts[old] == 0:
            del counts[old]
        left += 1
    best = max(best, right - left + 1)
print(best)

This prints 3. Keeping a zero-count key would make len(counts) cease to mean the number of distinct values in the window.

Why may the discarded starting positions stay discarded? Extending the right boundary cannot reduce the number of distinct values. Any start already invalid for this right boundary stays invalid for later right boundaries. This monotonic property lets the left boundary move forward permanently. Record an answer only after restoring the invariant: the current window contains at most k distinct values.

Knowing when a window is valid

Enumerating O(n²) ranges and constructing a set for each can cost O(n³). Even an incremental-count baseline for each start costs O(n²). The sliding method performs at most n right moves and n left moves, so expected time is O(n) with hash-map operations. Keeping only positive counts uses O(k+1) live map entries during expansion, bounded by the input's distinct count.

This is a maximum length, not a count of all valid ranges or a subsequence with gaps. Do not apply the same shrink rule to arbitrary constraints. For example, sum thresholds with negative numbers can become valid again after adding a value, breaking the monotonic argument. For a tiny input, enumerating ranges is a useful correctness baseline. For a fixed-length numeric window, a running sum may be all the state you need.

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