Sliding Window

Reader guide and study workflow · Complete course map

A stream reports positive costs [3,1,2,5,1]. Find the shortest consecutive segment totaling at least 7. A segment is contiguous: choosing the 5 and an unrelated earlier 3 is not enough unless every value between them is included.

Derive what can leave the window

The simple model lists every start and end, computes each segment's sum, and keeps the shortest qualifying length. Prefix sums remove repeated addition but still leave quadratically many candidate segments. We need a reason to stop reconsidering old starts.

Extend a running segment from the left: sums become 3, 4, 6, then 11. At 11, record length 4 before removing anything. Removing 3 leaves sum 8 and length 3; removing 1 leaves sum 7 and length 2; removing 2 leaves sum 5 and ends the shrink phase. A removed start already produced a valid segment, and extending that same start later would only make it longer. It can be retired permanently.

This derives three pieces of state: left edge, current sum, and smallest recorded valid length. The right edge supplies new information; the left edge removes information that can no longer improve the answer. The stopping argument needs positive values: with [2,-2,7], target 7, stopping after removal makes the sum too small and hides the later singleton 7. Removing a negative would increase the sum.

Window code is therefore a consequence of two claims: updates maintain the summary exactly, and discarded starts never need to return. Minimum cover and longest uniqueness have different recording moments. The next workshop reconstructs those choices and then examines the special historical-frequency optimization.

Prerequisites and readiness

Know inclusive window length r-l+1, frequency vectors, and amortized counting. Be able to explain why each endpoint advances at most n times even when one loop is nested inside another.

Reasoning workshop: choose the direction of validity

Two superficially similar loops

Minimum-cover windows shrink while valid, recording a candidate before each removal. Longest-unique windows shrink or jump when invalid, recording after repair. On target 7 and numbers [2,3,1,2,4,3], the last extension creates sum 9 for [2,4,3]. Record length 3, remove 2, record length 2 for [4,3], then remove 4 and stop at sum 3. Updating only after removal would miss valid candidates or record an invalid one.

Positivity supplies the required monotonicity. A negative number can make removing the left endpoint increase the sum, so a positive-sum window template cannot be transferred unchanged to arbitrary integers. The nested shrink loop remains linear because left only moves forward; count pointer movements, not indentation levels.

A last-seen trace that catches a real bug

For abba, the states after each byte are:

Byte at right	Previous occurrence	Left after repair	Active substring
a at 0	none	0	a
b at 1	none	0	ab
b at 2	1	2	b
a at 3	0	2	ba

The old a is outside the active window. Assigning left=last+1 without a maximum would move left backward to 1 and reintroduce a duplicate b. This is a good reconstruction test because the incorrect implementation often passes abcabcbb.

Multiplicity and threshold crossings

For target AAC, a valid cover needs two A bytes and one C. AC has the right distinct letters but not enough occurrences. A formed counter changes only when a byte count crosses its required threshold. Surplus A bytes do not satisfy extra target kinds. For fixed-size anagrams, the condition is stronger: all 26 counts must be equal, not merely sufficient.

Empty patterns are part of this pack's published domain. CheckInclusion returns true for an empty pattern. FindAnagrams returns every empty boundary, including the position after the final byte. MinWindow returns an empty string for an empty target. These are different return contracts, not inconsistencies to erase by copying one early-return branch everywhere.

The stale-maximum exception

Character Replacement is deliberately subtler. An exact maximum frequency would certify current validity. The optimized reference stores a historical nondecreasing maximum, so a retained window can be invalid even while length-maxFreq<=k holds. Its length never needs to decrease: one new byte increases length by one, and at most one left removal repairs the historical cap. A stale maximum cannot let the best grow beyond its current cap. Growth past that cap requires a newly observed actual frequency. Explain this distinction before treating the code as another “always valid window” template. A scan recomputing the maximum of 26 counts is also O(n) and offers a simpler correctness argument, though with a larger constant.

Word alignment and hashing cost

For word length 3, starts belong to offsets 0, 1, or 2. Scan each token stream separately. The text xbarfoo contains a match at offset 1, so scanning only multiples of three misses it. A foreign token clears the current stream's window; a repeated known token merely shrinks until its count is legal. Fresh reset maps should not preallocate the entire dictionary capacity on every foreign token.

A string-map lookup hashes the word's bytes. “Linear” here treats word length as fixed; with N text bytes and L-byte words, the bound is O(NL) expected plus dictionary construction. Separating token count from token comparison cost is a transferable complexity habit.

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

Pattern A: Variable window for "at least" constraints (minimum length)

Use when: you need the smallest window with sum >= target or a multiset coverage requirement.

Invariant: window state exactly represents s[l..r], and you shrink while the condition is satisfied to keep it minimal.

Skeleton:

l = 0
for r in 0..n-1:
    add(s[r])
    while windowValid():
        updateAnswer(l, r)
        remove(s[l])
        l++

Problems:

• minimum-size-subarray-sum: shrink while sum >= target.
• minimum-window-substring: shrink while all required counts are covered.

---

Pattern B: Variable window for longest with uniqueness

Use when: the window must have no duplicates and you want the longest length.

Invariant: l is always the smallest left index such that s[l..r] has no duplicates.

Skeleton (last-seen jump):

last = map[char]int
l = 0
for r in 0..n-1:
    if s[r] in last:
        l = max(l, last[s[r]] + 1)
    last[s[r]] = r
    best = max(best, r-l+1)

Problems:

• longest-substring-without-repeating-characters.

---

Pattern C: Fixed-size window with counts

Use when: window length is fixed and you need a count match (anagrams / permutation).

Invariant: the window length stays equal to k; counts always match s[l..r].

Skeleton:

init counts for first k chars
check()
for r in k..n-1:
    add(s[r])
    remove(s[r-k])
    check()

Problems:

• permutation-in-string.
• find-all-anagrams-in-a-string.

---

Pattern D: Replacement budget window

Use when: you can replace at most k characters to make the window valid.

Optimization invariant: the maintained length is at most historical maxFreq+k. With a stale maximum, the current window need not be truly valid; the proof below concerns the best length.

Skeleton:

counts = map
maxFreq = 0
l = 0
for r in 0..n-1:
    counts[s[r]]++
    maxFreq = max(maxFreq, counts[s[r]])
    while (r-l+1) - maxFreq > k:
        counts[s[l]]--
        l++
    best = max(best, r-l+1)

Problems:

• longest-repeating-character-replacement.

---

Pattern E: Multi-word fixed window

Use when: window consists of fixed-size words (concatenation of all words).

Invariant: you slide in steps of wordLen and keep counts for each word.

Skeleton (per offset):

if words is empty: return []
wordLen = len(words[0])  // all words have equal length
if wordLen == 0: return []
totalWords = len(words)
if totalWords > len(s) / wordLen: return []
for offset in 0..wordLen-1:
    l = offset
    reset counts
    for r = offset; r + wordLen <= len(s); r += wordLen:
        word = s[r:r+wordLen]
        if word is absent from need:
            clear counts; l = r+wordLen; continue
        add word
        while counts[word] > need[word]:
            remove s[l:l+wordLen]
            l += wordLen
        if (r + wordLen - l) / wordLen == totalWords:
            record l

The loop admits only complete tokens. For text barfo and word length 3, bar is readable but the trailing fo is not another token. Count window length in words when comparing it with totalWords; a byte length must instead be compared with totalWords*wordLen.

Problems:

• substring-with-concatenation-of-all-words.

---

When to use Sliding Window (checklist)

• The query is about contiguous subarrays or substrings.
• You can maintain the required condition with incremental updates.
• A brute-force scan is too slow (O(n^2) or worse).

Common failures (checklist)

• Updating the answer after shrinking (min window) instead of before.
• Forgetting to update counts symmetrically on add/remove.
• Not jumping l past the last occurrence in uniqueness problems.
• Mishandling fixed-size windows (off by one in slide).
• Treating word-sized windows like character-sized windows.

Problem mapping

• minimum-size-subarray-sum: variable window with sum constraint.
• minimum-window-substring: variable window with required counts.
• longest-substring-without-repeating-characters: last-seen window.
• longest-repeating-character-replacement: replacement budget window.
• permutation-in-string: fixed-size count match.
• find-all-anagrams-in-a-string: fixed-size count match.
• substring-with-concatenation-of-all-words: word-sized sliding blocks.

Reconstruction lab

1. List all anagram starts for text aaaa, pattern aa.
2. Give a two-letter target multiset where a set-based minimum-cover test fails.
3. Explain why two pointers that each move at most N times give O(N) window updates, despite a nested loop.

Model answers

The starts are 0, 1, and 2; overlapping matches are distinct outputs.

Target AAC and window AC have the same distinct letters but different multiplicities. The window is not a cover.

Charge each extension to its entering position and each removal to its leaving position. No position enters or leaves more than once per stream, so there are at most 2N updates. Expensive hashing or rescanning inside an update must be counted separately.

Problems in this module

• Minimum Size Subarray Sum
• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Permutation in String
• Find All Anagrams in a String
• Minimum Window Substring
• Substring with Concatenation of All Words

Interactive checkpoint

Open the Sliding Window quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable