Common Sliding Window Patterns

The strongest signal is contiguity. If the problem asks about a subarray, substring, consecutive segment, or range of nearby indices, consider sliding window before dynamic programming or general recursion. The second signal is an updateable condition: sum, count, distinct values, maximum, minimum, replacement budget, or required characters.

The third signal is monotonic repair. After expanding right, can moving left forward restore or improve the condition without needing to revisit earlier right endpoints? If yes, a sliding-window template is likely available.

Common templates include:

• Longest valid window: expand right, shrink while invalid, then maximize right - left + 1. Signal: longest substring or subarray satisfying at most, no repeats, or budget constraints.
• Shortest valid window: expand right until sufficient, update answer, then shrink while still sufficient. Signal: minimum length, smallest substring, or cover all requirements.
• Fixed-k aggregate: keep exactly k elements and update by adding entering plus removing leaving. Signal: length k, average of k, maximum sum of size k, or nearby within k.
• Count with exactly K: compute atMost(K) - atMost(K - 1) when direct exact counting is hard. Signal: exactly k distinct, exactly k odds, or exact binary sum variants.
• Monotonic-deque max or min: maintain candidates in decreasing or increasing order while endpoints slide. Signal: maximum or minimum inside every window of size k or inside a bounded range.

The invariant chooses the template. If the statement says at most, no more than, or budget not exceeded, the invariant is usually a validity ceiling and the answer may be longest or counted. If the statement says at least, contains all, or covers target, the invariant is usually a sufficiency condition and the answer may be shortest.

For exact constraints, ask whether exact is easier as a difference of two at-most counts. This is especially useful when every window counted by atMost(K) contains all windows with fewer than K, so subtracting removes the smaller cases and leaves exactly K.

Start by naming the contiguous range and the state it carries. Then state the invariant and explain why moving left forward repairs or tightens it. Finally, justify linear time by saying each element enters once through right and leaves once through left.

This explanation is more valuable than memorizing syntax. Senior interviews often combine patterns, such as a variable window with a frequency map or a fixed window with a deque. If you can name the invariant and the endpoint updates, you can adapt the template under pressure.