The Sliding Window Pattern: One Template, Many Problems

Any time a problem asks about a contiguous subarray or substring — the longest, shortest, or one with some property — think sliding window. Instead of checking every start and end pair (O(n²)), you move two pointers forward once each: O(n).

Recognise it

Look for:

• "contiguous subarray / substring";
• "longest / shortest / maximum / minimum … such that …";
• a condition you can update incrementally when one element enters or leaves.

If elements can be negative and you need exact sums, sliding window usually doesn't work (the window's validity isn't monotonic). Use prefix sums with a hash map instead.

Template 1: fixed-size window

The window always has exactly k elements: add the new element, remove the one that fell out.

// Maximum sum of any subarray of size k
int maxSum(int[] a, int k) {
    int sum = 0, best = Integer.MIN_VALUE;
    for (int r = 0; r < a.length; r++) {
        sum += a[r];                          // element enters
        if (r >= k) sum -= a[r - k];          // element leaves
        if (r >= k - 1) best = Math.max(best, sum);
    }
    return best;
}

Template 2: variable-size window

Expand r every step; shrink l while the window is invalid (or, for "shortest" problems, while it's still valid).

int l = 0;
for (int r = 0; r < n; r++) {
    add(a[r]);                     // update the window state
    while (windowInvalid()) {      // shrink until valid again
        remove(a[l++]);
    }
    best = Math.max(best, r - l + 1);
}

The whole trick is choosing the window state (a sum, a count map, the number of distinct characters) so that add, remove and the validity check are O(1).

Six worked problems

1. Longest substring without repeating characters

State: the last index of each character. When a repeat appears inside the window, jump l past its previous position.

int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];
    Arrays.fill(last, -1);
    int best = 0;
    for (int l = 0, r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (last[c] >= l) l = last[c] + 1;
        last[c] = r;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

2. Minimum size subarray with sum ≥ target (positive numbers)

A "shortest" problem: shrink while the window is valid, recording the length each time.

int minSubArrayLen(int target, int[] a) {
    int l = 0, sum = 0, best = Integer.MAX_VALUE;
    for (int r = 0; r < a.length; r++) {
        sum += a[r];
        while (sum >= target) {
            best = Math.min(best, r - l + 1);
            sum -= a[l++];
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

3. Longest substring with at most K distinct characters

State: a count map. Invalid when map.size() > k.

int longestKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        count.merge(s.charAt(r), 1, Integer::sum);
        while (count.size() > k) {
            char c = s.charAt(l++);
            if (count.merge(c, -1, Integer::sum) == 0) count.remove(c);
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

4. Longest repeating character replacement

You may replace up to k characters. The window is valid while windowLength − maxFrequency ≤ k.

int characterReplacement(String s, int k) {
    int[] freq = new int[26];
    int l = 0, maxFreq = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        maxFreq = Math.max(maxFreq, ++freq[s.charAt(r) - 'A']);
        while (r - l + 1 - maxFreq > k) freq[s.charAt(l++) - 'A']--;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

(maxFreq never needs to decrease: the answer only grows when a larger frequency appears.)

5. Find all anagrams of p in s

A fixed window of size |p|; compare 26-letter counts. A running "matches" counter makes each step O(1).

6. Minimum window substring

The classic hard problem: expand until the window covers every needed character (a missing counter reaches 0), then shrink from the left while it still covers them, recording the best window. O(|s| + |t|).

Complexity

Each index enters the window once and leaves at most once, so the pointers move O(n) times in total, even with the inner while loop. Space is O(k) or O(alphabet size) for the window state.

Common mistakes

• Using a sliding window on arrays with negative numbers for sum conditions (use prefix sums).
• Forgetting to update the answer in the right place: after shrinking for "longest", inside the shrink loop for "shortest".
• Recomputing the window state from scratch each step, which makes it O(n·k) again.

Follow-up questions this topic invites — and their answers

Q: Sliding window vs two pointers — what's the difference? A: A sliding window is a two-pointer technique where both pointers move in the same direction and the elements between them form the window. Other two-pointer problems move the pointers toward each other (e.g. pair sum in a sorted array).

Q: How do I handle "exactly K distinct"? A: exactly(K) = atMost(K) − atMost(K − 1), using the at-most-K template twice.

Q: What about the maximum in every window of size k? A: A plain window can't track the max when elements leave. Use a monotonic deque of indices, which is O(n) overall.

Practise these and more in the sliding window pattern lesson and the DSA problem set.