Sliding Window

Best sum of any 3 consecutive days, brute force:

def best_3_days(nums):
    best = float("-inf")
    for i in range(len(nums) - 2):
        best = max(best, nums[i] + nums[i+1] + nums[i+2])   # re-adds 3 values
    return best

Look at consecutive windows: [a, b, c] then [b, c, d]. They share b + c — two thirds of the work — yet brute force throws that away and re-sums. For window size k that's O(n · k); for variable-size windows the naive version is O(n²) or O(n³).

The fix is an accounting trick: keep a running total and repair it as the window slides.

window = sum(nums[:3])
best = window
for i in range(3, len(nums)):
    window += nums[i] - nums[i - 3]   # one enters, one leaves
    best = max(best, window)

Every element enters the window once and leaves once. Total work: O(n), regardless of k.

Principle: when consecutive subproblems overlap almost entirely, don't recompute — maintain a running state and apply the delta.

Sliding windows come in two builds, and identifying which one you need is half the problem:

Fixed-size — the problem names a width: "any k consecutive days", "every substring of length k". The loop is rigid: slide right by one, add the entering element, remove the leaving one. There's exactly one window per position; no decisions to make.

Variable-size — the problem says "longest" or "shortest" subject to a condition: longest substring with no repeats, smallest window containing all required letters. Now the window breathes. The skeleton:

left = 0
for right in range(len(s)):
    # 1. absorb s[right] into the window state
    while window_is_invalid():
        # 2. evict s[left] from the state
        left += 1
    # 3. window [left..right] is valid — record it

The right pointer is greedy: it always advances, always expands. The left pointer only moves to restore validity. Both pointers move at most n times, so despite the nested look, it's O(n) — a fast/slow pointer pair wearing different clothes.

Spot the variant fast: a number k in the statement means fixed; the words longest / shortest / at most / at least mean variable.

Variable windows live or die by one discipline — the invariant: a property of [left..right] that is true every time you reach the bottom of the loop.

For "longest substring without repeating characters" the invariant is the window contains no duplicates. The loop is a negotiation with it:

def longest_clean(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1      # shrink just enough to restore the invariant
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Expanding may break the invariant; shrinking restores it — and you shrink the minimum amount necessary, never more. Because the window is valid at every measurement point, taking max (or min, for "shortest" problems) over those points is guaranteed to see the optimum.

Why is no answer missed when left advances? Because the window only shrinks when keeping left makes validity impossible — every window starting at the abandoned positions and extending past right would be invalid too. Same discard logic as two pointers: each move must come with a one-sentence proof that nothing valid was skipped.

Principle: name the invariant before you code. Expand greedily, shrink minimally, measure only when valid.

The pointers define where the window is; the state says what's in it — and the state must support O(1) updates on enter and leave, or your O(n) claim collapses.

The counts dict is the workhorse. The cardinal rule: mirror every entry with an exit.

counts = {}
left = 0
for right, ch in enumerate(s):
    counts[ch] = counts.get(ch, 0) + 1          # enter
    while len(counts) > k:                       # invariant: at most k distinct
        ev = s[left]
        counts[ev] -= 1                          # leave
        if counts[ev] == 0:
            del counts[ev]                       # critical: 0 is not "absent"
        left += 1

That del is where most sliding-window bugs live — a zero-count key silently inflates len(counts) and your "distinct items" check lies to you. For harder problems (minimum window substring), add a single matched counter so checking "is the window valid?" stays O(1) instead of rescanning the dict.

Principle: the window is a tiny database. Every insert needs a matching delete, and validity checks must be O(1).