Sliding window without the guesswork

Oct 18, 2026 · @Utkarsh Shrivastava

Sliding window turns "check every subarray" (O(n²)) into one pass (O(n)). Grow the window on the right, shrink it on the left, and keep state you can update in O(1).

1. Spot it

Use a sliding window when all three are true:

• The answer is a contiguous subarray or substring.

• You want the longest, shortest, a count, or every window of size k.

• Adding or removing one element updates your state in O(1).

Watch out for subarray sums with negative numbers. Growing the window doesn't always grow the sum, so use prefix sums instead.

2. Fill three blanks

Before coding, write down:

1. State: what you track, like letter counts, a sum, or a set.

2. Valid: when the window is OK, like size - max(counts) <= k.

3. Goal: longest, shortest, count, or fixed size. This picks your template.

3. Pick a template

Every loop adds right, shrinks from left, and updates the answer. The goal only changes when you shrink and where you update.

Longest

left = 0
for right in range(len(s)):
    add(s[right])
    while not valid():
        remove(s[left])
        left += 1
    best = max(best, right - left + 1)

Practice: 3. Longest Substring Without Repeating Characters, 424. Longest Repeating Character Replacement

Shortest

left = 0
for right in range(len(s)):
    add(s[right])
    while valid():
        best = min(best, right - left + 1)
        remove(s[left])
        left += 1

Practice: 209. Minimum Size Subarray Sum, 76. Minimum Window Substring

Count

left = 0
for right in range(len(s)):
    add(s[right])
    while not valid():
        remove(s[left])
        left += 1
    total += right - left + 1   # every valid window ending at right

For "exactly k", count at_most(k) - at_most(k - 1).

Practice: 713. Subarray Product Less Than K, 992. Subarrays with K Different Integers

Fixed size k

for right in range(len(s)):
    add(s[right])
    if right >= k:
        remove(s[right - k])        # the element leaving
    if right >= k - 1:
        best = max(best, state())

Practice: 567. Permutation in String, 239. Sliding Window Maximum (needs a monotonic deque)

4. Test it

Trace three inputs by hand, writing left, right, and the answer at each step:

1. The given example. Your trace should match the expected output.

2. Everything valid, like AAAA. The answer should be the whole input.

3. Tiny input, like one element or an empty string. No crash, and the answer is 0 or 1.

Then check one rule: each element is added once and removed at most once. If something is added twice, right is moving wrong.