Sliding Window

Fixed-size sliding window computes running aggregates in O(n). Core optimization pattern.

mx = cur = sum(a[:k])
for i in range(k, len(a)):
    cur += a[i] - a[i-k]
    mx = max(mx, cur)

Single-pass tracking of running minimum and maximum profit. Classic greedy O(n) solution.

mn = float('inf')
mx = 0
for p in prices:
    mn = min(mn, p)
    mx = max(mx, p - mn)

The generic expand-right / shrink-left template handles all variable-length window problems.

l = 0
for r in range(len(s)):
    # add s[r]
    while invalid():
        # remove s[l]
        l += 1

Hash-map window tracks last index of each char. Avoids set removal on duplicates.

seen = {}
l = res = 0
for r, c in enumerate(s):
    if c in seen and seen[c] >= l:
        l = seen[c] + 1
    seen[c] = r
    res = max(res, r - l + 1)

Counter-based fixed window slides character frequencies. Powers anagram detection.

from collections import Counter
w = Counter(s[:k])
for i in range(k, len(s)):
    w[s[i]] += 1
    w[s[i-k]] -= 1
    if w[s[i-k]] == 0: del w[s[i-k]]

Tracking have/need counts is the matching logic inside minimum-window-substring.

need, have = len(cnt_t), 0
for c in window:
    window_cnt[c] += 1
    if window_cnt[c] == cnt_t[c]:
        have += 1

Monotonic deque keeps the running maximum in O(1) per step. Key for window-maximum.

from collections import deque
d = deque()
for i, x in enumerate(a):
    while d and a[d[-1]] <= x: d.pop()
    d.append(i)
    if d[0] <= i - k: d.popleft()

Window is valid when (window_size - max_freq) <= k. max_freq only needs to increase — shrinking the window can't help.

count = {}
l = max_freq = 0
for r in range(len(s)):
    count[s[r]] = count.get(s[r], 0) + 1
    max_freq = max(max_freq, count[s[r]])
    if (r - l + 1) - max_freq > k:
        count[s[l]] -= 1
        l += 1