Sliding Windows

Sliding windows avoid rescanning overlapping contiguous ranges. They work when moving a boundary updates the needed state cheaply and the validity condition tells you which boundary can move without losing an answer.

1. Check the Condition Before Choosing a Template

Use [left,right] for the nonempty current window in the scans below. Add the new right element, then apply the rule for the objective.

For a fixed window sum, initialize from the first k items, then add the entering value and subtract the leaving one. Initialize a maximum from a real window, not zero, because all sums may be negative. Define the result when k <= 0 or k > n.

A disqualifying element that no valid window may contain allows a full reset: set left = right+1 and clear state. This is a special case of shrinking, useful for consecutive-streak constraints.

2. Longest Valid and Shortest Sufficient Windows

For Longest Substring Without Repeating Characters, adding one character can create a duplicate. Shrink until it disappears; then the remaining window is the longest valid suffix ending here.

def longest_unique(text):
    counts = {}
    left = best = 0
    for right, char in enumerate(text):
        counts[char] = counts.get(char, 0) + 1
        while counts[char] > 1:
            old = text[left]
            counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
        best = max(best, right - left + 1)
    return best

The previous window had no duplicates, so only the entering character can violate the condition. Both boundaries only move forward: expected $O(n)$ time, $O(U)$ space for at most U distinct characters. When a last-seen-index variant jumps left, use max(left, last_seen[char]+1) so it never moves backward.

For Minimum Size Subarray Sum, assume nonnegative values and positive target. Add into total; while total >= target, record the length before subtracting the leftmost value and advancing left. This checks every promising shorter suffix before it becomes insufficient. Time is $O(n)$, auxiliary space $O(1)$; keep a sentinel for “no valid window.”

For minimum coverage of a target multiset, keep required frequencies and a count of fulfilled requirements. Shrink while all are fulfilled, updating that count only when a frequency crosses its required threshold. Presence alone is insufficient when the target repeats a character.

3. Count All Valid Starts, Then Derive Exactly K

Suppose a bad day has sales below 10. Maintain at most k bad days. After repairing the window, every start between left and right gives a valid subarray ending at right, hence right-left+1 new answers.

def at_most_bad_days(sales, k):
    if k < 0:
        return 0
    left = bad = answer = 0
    for right, value in enumerate(sales):
        bad += value < 10
        while bad > k:
            bad -= sales[left] < 10
            left += 1
        answer += right - left + 1
    return answer

• Exactly k = at_most(k) - at_most(k-1).
• At least k = n*(n+1)//2 - at_most(k-1) for k >= 0.

The k < 0 guard is necessary when deriving exactly zero. This counts nonempty subarrays, uses $O(n)$ time and $O(1)$ space, and may return a value of order $n^2$. For distinct-value counts, replace the bad-day counter with frequencies and remove zero-count keys. The same subtraction works for integer-valued counts, not arbitrary window objectives.

4. Know When the Window Argument Fails

For a sum limit of 3, [4] is invalid but extending it to [4,-2] makes it valid. Discarding the first element when the sum exceeds the limit loses answers. Likewise, finding a shortest target-sum window cannot rely on ordinary shrinking with negative values. Use Prefix Sums for exact sums with signed inputs; other signed-sum objectives may require a monotonic deque.

Validity alone does not guarantee linear time. Recomputing max(window) or comparing an entire frequency map on every move repeats work. For a fixed-window maximum, keep indices in decreasing value order in a deque: discard expired indices at the front and smaller or equal candidates at the back; a newer, larger value makes those older candidates useless for all future windows. Each index enters and leaves once, giving $O(n)$ total time and $O(k)$ space. This is a next step into monotonic stacks and queues.

5. Key Takeaways

• Longest valid: record after shrinking invalidity away. Shortest sufficient: record while still valid, before shrinking.
• For at-most counts, add every valid start, right-left+1, not just one answer per endpoint.
• Define at_most(-1)=0 before deriving exactly zero.
• Negative numbers break sum monotonicity, not every sliding-window problem. Verify the actual validity condition and update cost.

Review Two Pointers for boundary progress and Sets & Maps for frequency state. Use Binary Search if feasibility is monotonic in an answer value but a direct moving window is unsuitable.