Sliding Window

Sliding window turns O(n^2) substring scans into O(n) by maintaining a moving range [l..r] and a small summary state (sum, counts, or last-seen indices). The only two operations are to extend right (add one element) and shrink left (remove one element).

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.

Invariant: window is valid when (window length - maxFreq) <= k.

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):

for offset in 0..wordLen-1:
    l = offset
    reset counts
    for r in offset..n-1 step wordLen:
        word = s[r:r+wordLen]
        add word
        while counts[word] > need[word]:
            remove s[l:l+wordLen]
            l += wordLen
        if window length == totalWords:
            record l

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.