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

Find the longest contiguous range whose distinct-label count stays within a limit. Repeated occurrences of a label still occupy positions but contribute only one distinct key.

Enumerating ranges and rebuilding sets repeats work. A moving window can retain counts while advancing both boundaries. Removing one occurrence must not remove the label until its count reaches zero.

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.

A window map owns counts inside [left,right]. Removing a label decrements one occurrence; it removes the distinct entry only at zero. Shrink until the distinct bound holds before recording the length. Each element enters and leaves once: expected O(n) time and O(k) active counts.

This single boundary update illustrates the difference between occurrence count and distinct count:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>();
        counts.put("a", 2);
        counts.put("b", 1);
        counts.merge("a", -1, Integer::sum);
        assert counts.size() == 2;
        assert counts.get("a") == 1;
    }
}

The label a remains in the window after one occurrence leaves. Removing its map entry immediately would falsely claim the window has fewer distinct labels and could admit an invalid range. The complete exercise also needs the shrinking loop and best-length invariant.

Knowing when a window is valid

This pattern supports bounded-diversity windows in event streams, text analysis, and grouped activity. It applies when feasibility can be restored by moving the left boundary forward; arbitrary window predicates may not have that property.

Return the greatest contiguous length with at most limit distinct exact strings. Empty input and limit zero return zero. Negative limit raises IllegalArgumentException.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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