Lesson 3 of 16 Arrays and Strings

Sliding Window Pattern

Fixed and variable sliding windows explained: max sum of k elements, longest substring without repeats, and minimum window substring in Python.

40-50 min intermediate 0/16 lessons done
Course contents Lesson 3 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. Two kinds of window
  4. Code
  5. When sliding window doesn’t apply
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • Fixed-size versus variable-size windows.
  • The grow-right, shrink-left template.
  • Minimum window substring, a classic hard problem, step by step.

Signals

  • “Contiguous subarray or substring” plus “longest”, “shortest”, “maximum sum”, “at most K distinct”.
  • A brute force that recomputes something for every (start, end) pair.

Two kinds of window

  • Fixed size k: slide one step at a time, add the entering element and remove the leaving one. O(n).
  • Variable size: expand right every step; while the window breaks (or satisfies) a condition, move left. Each index enters and leaves once, so O(n) despite the nested loop.
left = 0
for right, x in enumerate(items):
    add(x)
    while window_invalid():
        remove(items[left])
        left += 1
    update_answer(left, right)

Code

"""Sliding window: fixed-size and variable-size windows over arrays and strings."""
from collections import Counter


def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]  # slide: add the new element, drop the old one
        best = max(best, window)
    return best


def longest_unique_substring(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1  # jump past the previous copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def min_window(s, t):
    need, missing = Counter(t), len(t)
    left, best = 0, (0, float("inf"))
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:  # valid window: try to shrink it
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[1] == float("inf") else s[best[0]: best[1] + 1]


if __name__ == "__main__":
    print(max_sum_k([2, 1, 5, 1, 3, 2], 3))
    print(longest_unique_substring("abcabcbb"), longest_unique_substring("pwwkew"))
    print(repr(min_window("ADOBECODEBANC", "ABC")))

Output:

9
3 3
'BANC'
  • Max sum of k: one running sum, updated in O(1) per step.
  • Longest substring without repeats: remember each character’s last index; when it repeats inside the window, jump left past the old copy instead of shrinking one step at a time.
  • Minimum window substring: need counts what’s still required; missing counts how many characters are outstanding. When missing hits 0 the window is valid, so shrink from the left while it stays valid, recording the smallest.

When sliding window doesn’t apply

The shrink step needs monotonicity: making the window bigger must never make an invalid window valid again (or vice versa). With negative numbers, “subarray sum equals k” breaks that rule, and you need prefix sums instead.

When you need the maximum inside each window, a running variable isn’t enough; that’s the next lesson, sliding window maximum.

Practise: sliding window problems.

Key takeaways

  • Fixed windows: add one, remove one. Variable windows: grow right, shrink left while invalid.
  • Each index enters and leaves once, so the nested while loop is still O(n).
  • Track window state with counts or last-seen indices.
  • Sliding window needs monotonic validity; with negative numbers use prefix sums.

Exercises

  1. Longest substring with at most K distinct characters.
  2. Longest repeating character replacement (LeetCode 424).
  3. Find all anagrams of p in s using a fixed window of counts.

Quiz

  1. Why is the variable window O(n) despite a while loop inside a for loop?
  2. Why can’t sliding window solve “subarray sum equals k” with negative numbers?
  3. In minimum window substring, what does missing == 0 mean?
Show answers
  1. left only moves forward and never past right, so across the whole run it moves at most n times.
  2. Adding a negative number can make a too-large sum valid again, so shrinking isn’t safely monotonic.
  3. The current window contains every required character with enough multiplicity, so it’s a valid candidate.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).