Sliding window

You’ll recognise it when

• The answer is a contiguous piece: a subarray or a substring, not any subset.
• You want the longest or shortest piece with some property: no repeats, at most k distinct values, sum at least S.
• If a window is fine, every smaller window inside it is fine too (or, for “shortest” problems, every bigger one is).
• The brute force tries every start and every end, which is O(n²) or worse.

It’s often confused with prefix sums, which answer “what’s the sum of this range?” for any range. A window only moves forward, so it needs a rule that behaves nicely as it grows and shrinks.

The idea

Picture reading a long receipt through a cardboard tube you can stretch. You slide the far end forward one line at a time. If the tube now shows something it shouldn’t, say the same item twice, you pull the near end forward until it doesn’t. Neither end ever goes back.

That’s the whole technique. Two indexes, left and right, mark the window. right visits every position once. left only moves when the window breaks the rule, and it only moves forward. After each step the window is the longest valid window ending at right, so the best of those is the answer.

How it works

Here’s the pattern on one problem: the length of the longest substring with no repeated character. A count table says how many copies of each letter are inside the window.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the string: try abba, aaaa, or a word with no repeats.

Why it’s correct: after each step, the window is the longest one ending at right with no repeats. It can’t start earlier, because left only moved past a letter when keeping it meant a repeat, and a window that contains a repeat still contains it when you make it longer. Every substring ends somewhere, so checking the best window at each right checks them all.

def longest_unique(s):
    """Length of the longest substring of s with no repeated character."""
    count = {}                              # letter -> copies inside the window
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

#include <string>
#include <algorithm>
using namespace std;

// Length of the longest substring of s with no repeated character (ASCII).
int longestUnique(const string& s) {
    int count[128] = {};                          // copies of each char inside the window
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char ch = s[right];
        count[ch]++;
        while (count[ch] > 1) {
            count[s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

class LongestUnique {
    // Length of the longest substring of s with no repeated character (ASCII).
    static int longestUnique(String s) {
        int[] count = new int[128];                   // copies of each char inside the window
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            count[ch]++;
            while (count[ch] > 1) {
                count[s.charAt(left)]--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

The same skeleton solves most window problems. Only the rule changes:

left = 0
for right in range(len(a)):
    add(a[right])                 # expand
    while window_is_invalid():
        remove(a[left])           # shrink
        left += 1
    best = max(best, right - left + 1)   # record

When does it work? The rule must be monotone: if a window breaks it, every bigger window containing it breaks it too. “No repeats”, “at most k distinct” and “sum ≤ S with non-negative numbers” all qualify. “Sum ≤ S” with negative numbers doesn’t: adding a negative number can make a bad window good again, so shrinking can throw away the answer. Use prefix sums (with a sorted structure or a monotonic deque) for those.

Why it’s O(n)

There’s a loop inside a loop, but count how far the pointers move instead. right goes from 0 to n - 1 once. left also only goes forward, and never passes right + 1, so across the whole run the inner loop body runs at most n times in total.

That’s O(n) time. The count table holds one entry per distinct letter in the window: at most 26 for lowercase letters, 128 for ASCII.

Common mistakes

left = last[ch] + 1              # ✗ can move left backwards
left = max(left, last[ch] + 1)   # ✓ the window only moves forward

count[a[left]] -= 1                               # ✗ zero entries still counted
if count[a[left]] == 0: del count[a[left]]        # ✓ len(count) is the distinct count

Variations

• Fixed-size window. For every window of exactly k elements (a moving average, say), add a[right] and remove a[right - k] on every step. No shrink loop needed.
• Minimum window. For the shortest valid window, like the smallest substring containing all of t‘s letters, flip the loop: grow until valid, then shrink while it’s still valid, recording the answer inside the shrink loop.
• At most k distinct. Same template with len(count) > k as the rule. “Exactly k distinct” isn’t monotone, but it equals atMost(k) − atMost(k − 1).
• Sliding window maximum. For the max of every window of size k, keep a deque of indexes whose values decrease from front to back. Pop smaller values off the back before pushing, and pop the front when it falls out of the window. The front is always the max: O(n) overall.
• Jump with last-seen indexes. For the no-repeat problem, store each letter’s last index and set left = max(left, last[ch] + 1). Same O(n), one jump instead of a loop.