A window is two indexes and a promise: everything between them satisfies the rule. Keep the promise while both edges only ever move right, and "longest contiguous anything" collapses from O(n²) candidates to one O(n) pass.
Chapter 5's two pointers walked toward each other and met in the middle. This chapter's two pointers walk the same direction, dragging a stretch of the array between them like a caterpillar — front end inches forward, back end catches up only when it must. That one picture solves everything the bank phrases as "longest/shortest substring or subarray such that…".
The plan: why contiguity licenses the trick, the grow/shrink loop and its invariant, the flagship no-repeats problem, fixed-width windows, the degenerate one-number window hiding inside Best Time to Buy & Sell Stock, the "shortest" mirror image, and then you take the wheel and try not to crash the window yourself.
Count the subarrays of an n-element array: one for every (start, end) pair — about n²/2 of them. The brute force checks each candidate, and checking usually costs O(n) itself, so you're staring at O(n³), or O(n²) with mild cleverness. For n ≈ 10⁵ (Chapter 3's budget math), both are dead on arrival.
The rescue comes from a fact so obvious it's easy to miss: consecutive candidates overlap almost completely. The subarray from index 2 to 9 and the subarray from 2 to 10 share eight elements. Recomputing from scratch throws that overlap away; a window keeps it. Slide the right edge one step and you've changed the candidate by exactly one element in and, sometimes, a few elements out. Update, don't rebuild.
Hence the caterpillar: two indexes l and r, and some cheap running summary of what's between them — a sum, a count map, a set. Both indexes only ever move right. That's the whole engine.
Every variable-width window problem is the same loop wearing different state. Pick an invariant — a property the window must satisfy ("no repeated characters", "sum ≤ S", "at most k zeros flipped"). Then:
The discipline is the pattern. Shrink too eagerly and you throw away the very window you were hunting; grow while broken and your "best" measurements are lies. Section 7's widget will happily flag you for both.
Longest Substring Without Repeating Characters Medium is the pattern's poster child. Invariant: every character in the window appears exactly once. State: the set of characters currently inside. The loop: try to grow; if the incoming character is already in the set, the invariant would break — so evict from the left until that older copy is gone, then grow.
Watch it run. The elastic band is the window; the braces below are its state; the green bracket marks the best window found so far. Notice the caterpillar rhythm — long greedy stretches of growth, short bursts of eviction — and notice that neither pointer ever backs up.
The widget shrinks one step at a time because that's the honest caterpillar. The production refinement — the one in Section 9's code — remembers each character's last seen index and jumps l straight past the stale copy in one assignment. Same invariant, same O(n), one fewer loop. Mention both in the room; the jump is a nice flex, the one-at-a-time version is easier to get right under pressure.
Sometimes the problem fixes the width and the elastic goes rigid: "maximum sum subarray of size k", or Permutation in String Medium — does any window of |s1| consecutive characters of s2 use exactly s1's letters? A fixed window is the easy case of the loop: every slide is add one element on the right, drop one on the left, both O(1) against the running state. No shrink loop at all — the widths never disagree.
For Permutation in String the state is a count map (Chapter 4's frequency counter, moonlighting). Keep a single integer matches — how many of the 26 letters currently have the correct count — and each slide touches at most two letters, so the check "is this window an anagram?" is matches == 26, O(1). Total: O(n) with a 26-entry map. The elegant part is what you don't do:
One fixed-width problem deserves a flag for later: Sliding Window Maximum Hard asks for the max of each window — and a max is the one summary you can't cheaply update when its element leaves. The fix is a monotonic deque that discards dominated elements, and it belongs to Chapter 8's monotonic-stack family. Park it; we'll collect it there.
Best Time to Buy & Sell Stock Easy: one buy, one later sell, maximize profit. It doesn't look like a window problem — until you ask what the best trade ending today is: today's price minus the cheapest price seen so far. The right edge is today; the left edge is wherever that minimum lives; and the entire window state has collapsed to a single number, min_so_far. One pass, two variables, O(n) — the caterpillar on a diet.
Scan the chart. The ochre staircase is min_so_far ratcheting downward; the green band is the best trade found so far. Watch the band jump when a new peak clears an old valley.
Minimum Window Substring Hard: the shortest window of s containing every character of t, multiplicity included. Same caterpillar, mirrored logic. For longest problems the window lives in a legal state and shrinking is an emergency. For shortest problems, being legal ("window covers all of t") is the goal, so the roles flip:
The state is two count maps and — same trick as Section 4 — a single integer have counting how many distinct characters currently meet their required count, so "is the window valid?" is have == need, O(1) per step. Total O(|s| + |t|). Candidates are recorded only inside the shrink phase, at the tightest moments — never while growing, when the window is carrying slack by construction.
There are exactly two ways to drive a window off the road, and interviewers see both weekly:
Drive it yourself: the invariant here is window sum ≤ 11, and the goal is the longest legal window. Grow and shrink by hand and the widget flags every infraction; or press Autopilot to watch the canonical loop drive it clean. The bar for a perfect run: match the optimal length with zero flags.
Notice what the autopilot never does: it never wonders whether to grow. Growth is unconditional; only the shrink is conditional. If your hand-rolled window code has an if deciding whether to advance r, you've usually smuggled in a bug.
The pattern has sharp borders, and knowing them is worth as much as knowing the loop:
The chapter's canon, in climbing order: Best Time to Buy & Sell Stock Easy, Longest Substring Without Repeating Characters Medium, Permutation in String Medium, Minimum Window Substring Hard, and Sliding Window Maximum Hard once Chapter 8 hands you the deque.
The pattern, as a whiteboard skeleton:
Longest Substring Without Repeating Characters Medium, both ways it appears on real whiteboards. First the canonical caterpillar — a set for state, an explicit shrink loop, exactly Section 2's skeleton. Then the refinement from Section 3: remember each character's last index and let l jump past the stale copy in one move. The Scala version wears the second form as a fold, because a window is secretly an accumulator: the state (l, best, lastSeen) threads through the string once.