Variable Window

In a variable-window problem, the size is not given. The algorithm discovers useful sizes while enforcing a condition. You may be asked for the longest substring with no repeated characters, the shortest subarray with sum at least a target, or the number of subarrays with at most k distinct values. In all of these, the window length is an output of the process, not an input.

The key question becomes: what makes the current window valid? Once that condition is clear, the algorithm alternates between expanding to discover more candidates and shrinking to repair or tighten the window.

The invariant is the promise your window keeps at the point where you update the answer. Examples include sum <= target, distinct count <= k, no character appears twice, or replacement cost <= k. The invariant should be specific enough that the answer update becomes obvious.

A strong variable-window explanation names the invariant in plain English before code. For longest-valid problems, update the best length after the repair loop has restored validity. For shortest-valid problems, update while the window is valid and shrink to see whether an even tighter answer exists.

Most variable-window templates move right exactly once per outer-loop iteration. That expansion includes a new element and may break the invariant. If the window becomes invalid, move left forward while undoing the leaving elements until validity returns.

This works when removing from the left cannot make the violation worse for the chosen condition. With positive numbers, removing values can reduce a too-large sum. With distinct counts, removing values can reduce the number of distinct keys. With duplicate-free substrings, removing characters can eliminate the extra copy.

The window state should answer validity quickly. A running sum handles positive-number sum limits. A set or frequency array handles uniqueness. A map from value to count handles distinct values. A maximum frequency can support replacement-style substring problems.

Do not track the entire window if a compact summary is enough. Sliding window is valuable because it turns a contiguous range into a maintained state. The best state is small, cheap to update when endpoints move, and directly tied to the invariant.