Sliding Window

What we're doing: Find the maximum sum of any contiguous size-k subarray.

def max_sum_fixed_window(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best


print(max_sum_fixed_window([2, 1, 5, 1, 3, 2], 3))

2

The first window is built once, the ordinary way — there is nothing to slide from yet.

4

nums[i] just entered the window; nums[i - k] just left it — exactly k elements are in the window at every step.

9

Why this works: The window [1, 5, 1] → sum 7 slides to [5, 1, 3] → sum 9 by removing the leading 1 and adding the trailing 3 — no resumming. 9 turns out to be the best of all four size-3 windows.

What we're doing: Find the length of the smallest contiguous subarray whose sum is at least a target.

def min_subarray_len(nums, target):
    left = 0
    window_sum = 0
    best = float("inf")
    for right in range(len(nums)):
        window_sum += nums[right]
        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return best if best != float("inf") else 0


print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))

6

right always extends the window, adding nums[right] to the running sum.

7

while, not if — the window keeps shrinking as long as it is still valid, since a smaller valid window is always at least as good.

9

Each shrink undoes exactly the sum contribution of the element leaving on the left.

2

Why this works: The window grows to [2, 3, 1, 2] (sum 8, width 4) before it first reaches the target, then keeps shrinking and re-extending as right advances — the smallest window found along the way is [4, 3] (sum 7, width 2).

What we're doing: Maintain a running character-frequency map for a fixed-size window as it slides, updating only what changed.

from collections import defaultdict


def window_char_counts(s, k):
    counts = defaultdict(int)
    for ch in s[:k]:
        counts[ch] += 1
    snapshots = [dict(counts)]
    for i in range(k, len(s)):
        counts[s[i]] += 1
        counts[s[i - k]] -= 1
        if counts[s[i - k]] == 0:
            del counts[s[i - k]]
        snapshots.append(dict(counts))
    return snapshots


for snap in window_char_counts("aabbcc", 3):
    print(snap)

6

Only the first window is built the ordinary way — one pass over its k characters.

8

Sliding by one only ever touches the two characters that changed: the one entering and the one leaving.

{'a': 2, 'b': 1}
{'a': 1, 'b': 2}
{'b': 2, 'c': 1}
{'b': 1, 'c': 2}

Why this works: The window starts at "aab" ({'a': 2, 'b': 1}). Sliding to "abb" only updates 'a' (leaving, 2→1) and 'b' (entering, 1→2). Sliding again to "bbc" fully removes 'a' the moment its count hits 0, rather than leaving a stale zero entry behind.

What we're doing: Find the length of the longest substring with no repeated character.

def length_of_longest_substring(s):
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


print(length_of_longest_substring("abcabcbb"))
print(length_of_longest_substring("bbbbb"))

5

last_seen[ch] >= left confirms the earlier occurrence is still inside the current window — an old occurrence before left is irrelevant.

6

Jumping directly to one past the duplicate skips every character in between in a single step, instead of removing them one at a time.

3
1

Why this works: "abcabcbb" has its longest duplicate-free run as "abc" (length 3) — every attempt to extend further immediately re-hits an already-seen character. "bbbbb" repeats "b" at every step, so the window can never grow past length 1.

What we're doing: Find the smallest substring of s that contains every character of t, including repeats.

from collections import Counter


def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    left = 0
    best_left, best_right = 0, 0
    for right, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if best_right == 0 or right - left < best_right - best_left:
                best_left, best_right = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[best_left:best_right]


print(min_window("ADOBECODEBANC", "ABC"))

8

missing counts required slots, not distinct characters — two required "A"s are two slots, both must be filled.

9

need[ch] going negative just means "more of this character than required is currently in the window" — that is fine, not an error.

10

missing == 0 means every required slot is currently filled somewhere in the window — the window just became valid.

12

Shrinking only pulls in characters the window has MORE than enough of (need[s[left]] < 0) — pulling in a still-needed character would break validity.

BANC

Why this works: "BANC" is the shortest substring of "ADOBECODEBANC" containing at least one A, one B, and one C — every shorter window either misses one of the three required characters or is not contiguous.

What we're doing: Find the length of the longest substring containing at most k distinct characters.

def longest_substring_k_distinct(s, k):
    counts = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:
            left_ch = s[left]
            counts[left_ch] -= 1
            if counts[left_ch] == 0:
                del counts[left_ch]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_substring_k_distinct("eceba", 2))

6

len(counts) is only accurate here because a key is deleted at count 0, not left sitting there.

9

The shrink loop runs until len(counts) is back within the limit, which for a single new character is at most one shrink.

3

Why this works: "ece" is the longest window in "eceba" using at most 2 distinct characters ('e' and 'c') — extending to include 'b' would introduce a third distinct character and force a shrink.