The Sliding Window Technique

Intermediate 13 min read

What you'll learn

✓When the sliding window technique applies
✓Fixed-size vs variable-size windows
✓How to design the expand and shrink invariants
✓How to use hash maps to track window state
✓Six classic interview problems and idiomatic solutions

Prerequisites

•Comfortable with two pointers — see Two Pointers
•Basic Python dictionaries and sets

The sliding window technique is what you reach for when a problem asks about a contiguous subarray or substring with some property — longest, shortest, max sum, count of valid ones. Like two pointers, it turns many O(n^2) brute-force scans into O(n) by maintaining one moving range instead of revisiting positions.

This post covers both flavours of window — fixed and variable — and the templates you can lift directly into interviews.

The core idea

A “window” is just a contiguous range [L, R] inside an array or string. The window slides forward by moving R (the right edge) one step at a time, and possibly advancing L (the left edge) to maintain some invariant.

There are two flavours:

Fixed-size window — R - L + 1 == k always. Slide it one step at a time.
Variable-size window — L and R move at independent rates, governed by a condition (e.g. “no duplicate characters in the window”).

The big payoff: when R advances and L only ever moves forward, each index enters and leaves the window at most once, giving O(n).

Fixed-size windows

The simplest pattern. Compute the answer for the initial window, then slide one step at a time, adding the new right element and subtracting the outgoing left element.

arr:  [ 2,  1,  5,  1,  3,  2 ]   target: max sum window of size 3
step 1: [ 2,  1,  5 ] 1   3   2     sum = 8
step 2:   2 [ 1,  5,  1 ] 3   2     sum = 7
step 3:   2   1 [ 5,  1,  3 ] 2     sum = 9   <— best so far
step 4:   2   1   5 [ 1,  3,  2 ]   sum = 6
answer = 9

A fixed window of size k=3 sliding across an array

def max_sum_subarray(arr, k):
    if len(arr) < k:
        return None
    window_sum = sum(arr[:k])
    best = window_sum
    for r in range(k, len(arr)):
        window_sum += arr[r] - arr[r - k]
        best = max(best, window_sum)
    return best

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))
# output: 9

The key trick is the rolling update: window_sum += arr[r] - arr[r - k]. We never re-sum the window from scratch.

Variable-size windows

Now the window grows and shrinks. The recipe:

Expand R one step at a time.
While the window violates the invariant, advance L until the invariant holds again.
Record the answer at every valid window.

s = “a b c a b c b b”
0 1 2 3 4 5 6 7
R=0   [a]                   set={a}             len=1
R=1   [a b]                 set={a,b}           len=2
R=2   [a b c]               set={a,b,c}         len=3  <— best
R=3   [a b c a]             duplicate ‘a’!
shrink L past first ‘a’:
_ [b c a]             set={b,c,a}         len=3
R=4   _ [b c a b]           duplicate ‘b’!
shrink past first ‘b’:
_ _ [c a b]           set={c,a,b}         len=3
…

A variable window expanding and shrinking to maintain 'no duplicates'

def longest_unique_substring(s):
    seen = {}
    L = 0
    best = 0
    for R, ch in enumerate(s):
        if ch in seen and seen[ch] >= L:
            L = seen[ch] + 1
        seen[ch] = R
        best = max(best, R - L + 1)
    return best

print(longest_unique_substring("abcabcbb"))
# output: 3
print(longest_unique_substring("pwwkew"))
# output: 3

seen maps each character to its most recent index. When the new character is already inside the window, we jump L past its old position. Each index is touched at most twice — once by R, once by L — so it is O(n).

The template

Most variable-window problems fit this skeleton:

def solve(arr):
    L = 0
    state = init_state()        # counter, set, sum, whatever
    best = 0
    for R, x in enumerate(arr):
        add_to_state(state, x)
        while not is_valid(state):
            remove_from_state(state, arr[L])
            L += 1
        best = max(best, R - L + 1)   # or min, or count
    return best

Once you internalise the shape, ninety percent of the work is choosing the right state and the right is_valid.

Try it yourself. Before reading on, sketch the state for “longest substring with at most k distinct characters.” You need a counter that tracks how many distinct characters are currently in the window. is_valid is len(counter) <= k.

When to reach for it

Look for these signals:

The problem asks about a contiguous subarray or substring.
Keywords like longest, shortest, maximum sum, at most k, exactly k.
A naive O(n^2) solution would try every starting index.
The property is monotonic with window size — once invalid, extending the window keeps it invalid, so shrinking is enough.

Practice problems

1. Maximum Sum Subarray of Size K

The fixed-window template above:

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for r in range(k, len(arr)):
        window_sum += arr[r] - arr[r - k]
        best = max(best, window_sum)
    return best

print(max_sum_subarray([2, 3, 4, 1, 5], 2))
# output: 7

2. Longest Substring Without Repeating Characters

Solved above. The variable window with a seen map.

3. Minimum Window Substring

Given strings s and t, find the smallest window in s that contains every character of t (with multiplicity).

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    L = start = 0
    best_len = float("inf")
    best = ""
    for R, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if R - L + 1 < best_len:
                best_len = R - L + 1
                best = s[L:R + 1]
            need[s[L]] += 1
            if need[s[L]] > 0:
                missing += 1
            L += 1
    return best

print(min_window("ADOBECODEBANC", "ABC"))
# output: BANC

missing is a fast scalar check; without it we would have to scan the whole counter each step.

4. Permutation in String

Return whether any permutation of t appears as a substring of s. Same as checking whether some window of size len(t) in s has the same character counts as t.

from collections import Counter

def check_inclusion(t, s):
    if len(t) > len(s):
        return False
    need = Counter(t)
    window = Counter(s[:len(t)])
    if window == need:
        return True
    for r in range(len(t), len(s)):
        window[s[r]] += 1
        window[s[r - len(t)]] -= 1
        if window[s[r - len(t)]] == 0:
            del window[s[r - len(t)]]
        if window == need:
            return True
    return False

print(check_inclusion("ab", "eidbaooo"))
# output: True

This is a fixed-size window — len(t) always — with a counter as the state.

5. Longest Repeating Character Replacement

Given a string and an integer k, you may replace any k characters. Return the length of the longest substring with all the same character after the replacements.

from collections import defaultdict

def character_replacement(s, k):
    count = defaultdict(int)
    L = 0
    best = 0
    max_freq = 0
    for R, ch in enumerate(s):
        count[ch] += 1
        max_freq = max(max_freq, count[ch])
        if (R - L + 1) - max_freq > k:
            count[s[L]] -= 1
            L += 1
        best = max(best, R - L + 1)
    return best

print(character_replacement("AABABBA", 1))
# output: 4

The window is valid when (size) - (most frequent count) <= k. Notice we never decrease max_freq even when shrinking — that is a subtle but correct optimisation: the answer can only improve from a bigger max_freq, so a stale one never causes a wrong answer.

6. Fruit Into Baskets

You can pick from at most two distinct fruit types. Find the longest contiguous run.

from collections import defaultdict

def total_fruit(fruits):
    count = defaultdict(int)
    L = 0
    best = 0
    for R, f in enumerate(fruits):
        count[f] += 1
        while len(count) > 2:
            count[fruits[L]] -= 1
            if count[fruits[L]] == 0:
                del count[fruits[L]]
            L += 1
        best = max(best, R - L + 1)
    return best

print(total_fruit([1, 2, 1, 2, 3, 2, 2]))
# output: 5

This is the canonical “at most k distinct” problem with k=2. Replace 2 with a variable and you have a one-line generalisation.

Try it yourself. Generalise total_fruit to “longest substring with at most k distinct characters.” Test it on ("eceba", 2) — the answer is 3 ("ece").

Common pitfalls

Off-by-one in fixed windows. The first full window covers arr[0:k]. The loop that slides should start at r = k.
Forgetting to delete zero counts. When using len(counter) <= k as your invariant, zero entries still count. Either delete them or use a separate distinct-counter.
Updating best outside the shrink loop. Record best only after the window is valid, otherwise you measure invalid windows.
Confusing “at most k” with “exactly k”. exactly_k = atMost(k) - atMost(k - 1) is a useful trick.

Recap

You now know:

A sliding window is a moving contiguous range [L, R].
Fixed-size: roll the sum/state, slide one step.
Variable-size: expand R, shrink L until invariant holds, record answer.
Both run in O(n) because each index enters and leaves the window at most once.
The template — state, is_valid, expand-then-shrink — covers most problems.

Next steps

Now that you can scan a window in linear time, the next step is being able to sort efficiently — the gateway to many other algorithms.

→ Next: Sorting Algorithms Overview

Questions or feedback? Email codeloomdevv@gmail.com.