Sliding Window: Efficient Subarray and Substring Problems

Look out of a train window. At every moment you see a frame of the landscape. As the train moves, one bit of scenery enters the frame at the front, and another bit leaves at the back. You do not re-photograph the whole view each second. You just update what changed.

That is the sliding window technique. For problems about contiguous ranges (subarrays and substrings), you keep a window [left, right] and a small summary of what is inside it: a running sum, a count, or a table of letter frequencies. When the window moves, you update the summary by adding the new element and removing the old one. Work that would be O(n) for each window becomes O(1), and the whole solution becomes O(n).

• The difference between fixed-size and variable-size windows.
• The expand-and-shrink template.
• Why the technique is O(n) even with a loop inside a loop.
• How to solve the classic problems: maximum sum of size k, smallest subarray with a given sum, longest substring without repeating characters, at most k distinct characters, and anagram search.
• When sliding windows are valid, and when negative numbers break them.

In a fixed-size window, the length k is given. The window slides one step at a time: the new element enters on the right, and the element k positions back leaves on the left.

Brute force. For each starting position, add up the next k elements: O(n × k).

Window. Compute the sum of the first k elements once. Then, for each next position, window = window + a[i] - a[i - k]. That is one addition and one subtraction per step.

Dry run on [2, 1, 5, 1, 3, 2] with k = 3:

The maximum is 9, from 5, 1, 3.

// File: Main.javapublic class Main {    // Brute force: O(n * k).    static long maxSumBrute(int[] a, int k) {        long best = Long.MIN_VALUE;        for (int start = 0; start + k <= a.length; start++) {            long sum = 0;            for (int i = start; i < start + k; i++) {                sum += a[i];            }            best = Math.max(best, sum);        }        return best;    }    // Sliding window: O(n) time, O(1) space.    static long maxSum(int[] a, int k) {        if (k <= 0 || k > a.length) {            throw new IllegalArgumentException("k must be between 1 and the array length");        }        long window = 0;        for (int i = 0; i < k; i++) {            window += a[i];                      // the first window        }        long best = window;        for (int i = k; i < a.length; i++) {            window += (long) a[i] - a[i - k];    // add the entering element, remove the leaving one            best = Math.max(best, window);        }        return best;    }    public static void main(String[] args) {        int[][] inputs = {{2, 1, 5, 1, 3, 2}, {1, 2, 3}, {-1, -2, -3, -4}, {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE}, {4, 9, 1}};        int[] ks = {3, 3, 2, 2, 1};        for (int t = 0; t < inputs.length; t++) {            System.out.println(maxSumBrute(inputs[t], ks[t]) + " " + maxSum(inputs[t], ks[t]));        }        try {            maxSum(new int[] {1, 2}, 3);        } catch (IllegalArgumentException e) {            System.out.println("error: " + e.getMessage());        }    }}

9 96 6-3 -34294967294 42949672949 9error: k must be between 1 and the array length

The code checks the edge cases the problem leaves open: k larger than the array, and k of zero or less. It also uses long sums, because three copies of Integer.MAX_VALUE clearly do not fit in an int. The time is O(n), because every element is added once and subtracted once, and the space is O(1).

Often the window size is not given. You want the longest window that satisfies a condition, or the shortest one. The window grows and shrinks as you scan.

The standard template:

left = 0for right from 0 to n - 1:    add a[right] to the window summary           // expand    while the window breaks the rule (or, for "shortest", while it meets the goal):        remove a[left] from the window summary   // shrink        left = left + 1    update the best answer using right - left + 1

• For "longest window that stays valid": expand always, shrink while the window is invalid, then record the length.
• For "shortest window that becomes valid": expand always, and while the window is valid, record its length and shrink.

Both left and right only ever move forward, and neither moves past n. The for loop moves right n times. The while loop moves left at most n times in total across the whole run, not per iteration. So the total number of pointer moves is at most 2n. This is the same amortised argument we used for the monotonic stack.

Problem. Given an array of positive integers and a target, find the length of the shortest contiguous subarray whose sum is at least the target, or 0 if none exists. For [2, 3, 1, 2, 4, 3] and target 7, the answer is 2 (4, 3).

Expand right, adding to sum. While sum >= target, record the window length and shrink from the left, subtracting a[left].

Dry run on [2, 3, 1, 2, 4, 3] with target 7:

The answer is 2.

The logic "once the sum reaches the target, we can shrink, and shrinking makes the sum smaller" depends on every element being non-negative. Then adding an element never decreases the sum, and removing one never increases it, so the window behaves predictably: growing helps reach the target, shrinking moves away from it.

With negative numbers that breaks. Removing a negative element raises the sum. Adding a negative one lowers it. A window that is currently below the target might become valid after dropping a negative element on its left, but the algorithm only shrinks when the sum is already at least the target. Here is a tiny counterexample: [-2, 6] with target 6. The shortest valid subarray is [6], length 1. The window algorithm sums -2, then 4, never reaches 6, never shrinks, and reports "none".

// File: Main.javapublic class Main {    // Positive numbers only. Returns 0 if there is no such subarray.    static int minLengthWindow(int[] a, long target) {        if (target <= 0) {            throw new IllegalArgumentException("target must be positive");        }        int best = Integer.MAX_VALUE;        long sum = 0;        int left = 0;        for (int right = 0; right < a.length; right++) {            sum += a[right];            while (sum >= target) {                best = Math.min(best, right - left + 1);                sum -= a[left];                left++;            }        }        return best == Integer.MAX_VALUE ? 0 : best;    }    // Works for any numbers, but O(n^2).    static int minLengthBrute(int[] a, long target) {        int best = Integer.MAX_VALUE;        for (int start = 0; start < a.length; start++) {            long sum = 0;            for (int end = start; end < a.length; end++) {                sum += a[end];                if (sum >= target) {                    best = Math.min(best, end - start + 1);                    break;                }            }        }        return best == Integer.MAX_VALUE ? 0 : best;    }    public static void main(String[] args) {        System.out.println(minLengthWindow(new int[] {2, 3, 1, 2, 4, 3}, 7) + " " + minLengthBrute(new int[] {2, 3, 1, 2, 4, 3}, 7));        System.out.println(minLengthWindow(new int[] {1, 1, 1, 1}, 11) + " " + minLengthWindow(new int[] {5}, 5) + " " + minLengthWindow(new int[] {}, 3));        System.out.println("with a negative number: window=" + minLengthWindow(new int[] {-2, 6}, 6) + " brute=" + minLengthBrute(new int[] {-2, 6}, 6));    }}

2 20 1 0with a negative number: window=0 brute=1

The last line shows the failure: the window answer 0 (no subarray) is wrong; the brute force correctly finds length 1. When numbers can be negative, sliding window sums are the wrong tool. Prefix sums with a hash map (next article) handle "sum equals k" with negatives, and a monotonic deque handles "sum at least k" with negatives, which is beyond this course.

The window summary does not have to be a number. For substring problems you keep whatever tells you if the window is valid: a set, a count of distinct characters, or a table of letter frequencies.

Problem. Find the length of the longest substring in which all characters are different. For "abcabcbb" the answer is 3 ("abc").

Brute force. Check every substring: O(n^2) or worse.

Window. Expand right. If s[right] already appears in the window, the window is invalid, so move left just past the previous occurrence of that character. Keep a map from each character to the last index where we saw it.

The subtle point: the previous occurrence might lie to the left of the window, in which case it is stale and must be ignored. So we only move left if the previous index is >= left.

Dry run on "abba", where the stale case appears:

The answer is 2. If we had blindly set left = 0 + 1 = 1 at the last step, the window would be "bba", which contains a repeat, and the answer would be wrongly 3. We use that mistake as an exercise.

Keep a frequency map for the window. Expand right, adding its character. While the map has more than k distinct keys, remove s[left] (decrease its count, and delete the key if it reaches zero) and advance left. The window is the longest valid one ending at right. For "eceba" with k = 2, the answer is 3 ("ece").

This is a fixed-size window of the pattern's length m, comparing letter counts. Maintain a count array for the window. At each step, add the entering character, remove the leaving one, and compare the window's counts with the pattern's counts. With 26 letters, the comparison is a constant 26 operations. For s = "cbaebabacd" and p = "abc", the answers are positions 0 ("cba") and 6 ("bac").

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main {    static int longestUnique(String s) {        Map<Character, Integer> last = new HashMap<>();      // character -> last index seen        int best = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            Integer previous = last.get(c);            if (previous != null && previous >= left) {      // only a repeat inside the window counts                left = previous + 1;            }            last.put(c, right);            best = Math.max(best, right - left + 1);        }        return best;    }    static int longestAtMostKDistinct(String s, int k) {        if (k == 0) {            return 0;        }        Map<Character, Integer> counts = new HashMap<>();        int best = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            counts.merge(s.charAt(right), 1, Integer::sum);            while (counts.size() > k) {                       // too many distinct characters: shrink                char leaving = s.charAt(left);                left++;                if (counts.merge(leaving, -1, Integer::sum) == 0) {                    counts.remove(leaving);                }            }            best = Math.max(best, right - left + 1);        }        return best;    }    // Lowercase letters only. Returns the start index of every anagram of p inside s.    static List<Integer> findAnagrams(String s, String p) {        List<Integer> result = new ArrayList<>();        int m = p.length();        if (m == 0 || m > s.length()) {            return result;        }        int[] need = new int[26];        int[] window = new int[26];        for (char c : p.toCharArray()) {            need[c - 'a']++;        }        for (int i = 0; i < s.length(); i++) {            window[s.charAt(i) - 'a']++;                      // character enters            if (i >= m) {                window[s.charAt(i - m) - 'a']--;              // character leaves            }            if (i >= m - 1 && Arrays.equals(window, need)) {                result.add(i - m + 1);            }        }        return result;    }    public static void main(String[] args) {        String[] tests = {"abcabcbb", "bbbbb", "pwwkew", "", "abba"};        StringBuilder out = new StringBuilder();        for (String t : tests) {            out.append(longestUnique(t)).append(' ');        }        System.out.println(out.toString().trim());        System.out.println(longestAtMostKDistinct("eceba", 2) + " " + longestAtMostKDistinct("aa", 1) + " " + longestAtMostKDistinct("abc", 0)                + " " + longestAtMostKDistinct("", 3) + " " + longestAtMostKDistinct("abaccc", 2));        System.out.println(findAnagrams("cbaebabacd", "abc") + " " + findAnagrams("abab", "ab") + " " + findAnagrams("a", "ab"));    }}

3 1 3 0 23 2 0 0 4[0, 6] [0, 1, 2] []

Complexity: each of these is O(n) time. longestUnique and longestAtMostKDistinct use O(min(n, alphabet)) extra space for the map, and the anagram search uses O(1) (two arrays of 26). The anagram window does O(26) work per step to compare arrays, a constant.

• The question is about a contiguous subarray or substring (not subsequences).
• You are asked for a longest, shortest, maximum, minimum or count of windows with some property.
• The property can be maintained incrementally when one element enters or leaves.
• The condition is monotonic: making the window bigger moves you consistently in one direction (more distinct characters, a larger sum of non-negatives), and shrinking moves you in the other.

If the problem is about all subarrays with an exact sum that may include negatives, or the property is not monotonic, think prefix sums and hashing instead.

• Applying a sum window to arrays with negative numbers. The shrink logic breaks.
• k bigger than the array, or k <= 0. Guard it.
• Off-by-one in the window length. The length of [left, right] is right - left + 1.
• Stale entries in a last-seen map. Move left only forward. Use max(left, previous + 1) or check previous >= left.
• Not removing zero counts from a frequency map, so that map.size() overstates the number of distinct characters.
• Forgetting to update the answer after shrinking (or before), depending on whether you maximise or minimise.
• Overflow. Running sums of ints can overflow, so use long.
• Resetting state wrongly. The window summary must be updated for both the element entering and the element leaving.
• Confusing a substring with a subsequence. A window is always contiguous.
• Empty input. The loops handle it, but check that your return value (such as 0 or an empty list) is what the problem expects.

static int longestUniqueBuggy(String s) {    Map<Character, Integer> last = new HashMap<>();    int best = 0;    int left = 0;    for (int right = 0; right < s.length(); right++) {        char c = s.charAt(right);        if (last.containsKey(c)) {            left = last.get(c) + 1;        }        last.put(c, right);        best = Math.max(best, right - left + 1);    }    return best;}

// File: Main.javapublic class Main {    public static void main(String[] args) {        int[] a = {1, 4, 2, 10, 2, 3, 1, 0, 20};        int k = 4;        long window = 0;        for (int i = 0; i < k; i++) {            window += a[i];        }        long best = window;        int bestStart = 0;        for (int i = k; i < a.length; i++) {            window += a[i] - a[i - k];            if (window > best) {                best = window;                bestStart = i - k + 1;            }        }        System.out.println(best + " starting at " + bestStart);    }}

24 starting at 5

// File: Main.javapublic class Main {    static boolean isVowel(char c) {        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';    }    static int maxVowels(String s, int k) {        int count = 0;        int best = 0;        for (int i = 0; i < s.length(); i++) {            if (isVowel(s.charAt(i))) {                count++;            }            if (i >= k && isVowel(s.charAt(i - k))) {                count--;                              // the character that just left the window            }            best = Math.max(best, count);        }        return best;    }    public static void main(String[] args) {        System.out.println(maxVowels("abciiidef", 3));        System.out.println(maxVowels("aeiou", 2));        System.out.println(maxVowels("leetcode", 3));        System.out.println(maxVowels("rhythms", 4));        System.out.println(maxVowels("", 3));    }}

32200

// File: Main.javapublic class Main {    static int longestOnes(int[] a, int k) {        int zeros = 0;        int best = 0;        int left = 0;        for (int right = 0; right < a.length; right++) {            if (a[right] == 0) {                zeros++;            }            while (zeros > k) {                if (a[left] == 0) {                    zeros--;                }                left++;            }            best = Math.max(best, right - left + 1);        }        return best;    }    public static void main(String[] args) {        System.out.println(longestOnes(new int[] {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2));        System.out.println(longestOnes(new int[] {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3));        System.out.println(longestOnes(new int[] {1, 1, 1}, 0));        System.out.println(longestOnes(new int[] {0, 0}, 0));    }}

61030

// File: Main.javaimport java.util.HashMap;import java.util.Map;public class Main {    static int longestUniqueBuggy(String s) {        Map<Character, Integer> last = new HashMap<>();        int best = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            if (last.containsKey(c)) {                left = last.get(c) + 1;            }            last.put(c, right);            best = Math.max(best, right - left + 1);        }        return best;    }    static int longestUniqueFixed(String s) {        Map<Character, Integer> last = new HashMap<>();        int best = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            if (last.containsKey(c)) {                left = Math.max(left, last.get(c) + 1);            }            last.put(c, right);            best = Math.max(best, right - left + 1);        }        return best;    }    public static void main(String[] args) {        System.out.println(longestUniqueBuggy("abba") + " " + longestUniqueFixed("abba"));        System.out.println(longestUniqueBuggy("abcabcbb") + " " + longestUniqueFixed("abcabcbb"));    }}

3 23 3

// File: Main.javapublic class Main {    // Assumes ASCII characters.    static String minWindow(String s, String t) {        if (t.isEmpty() || t.length() > s.length()) {            return "";        }        int[] need = new int[128];        for (char c : t.toCharArray()) {            need[c]++;        }        int missing = t.length();        int bestStart = 0;        int bestLength = Integer.MAX_VALUE;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char in = s.charAt(right);            if (need[in] > 0) {                missing--;            }            need[in]--;            while (missing == 0) {                if (right - left + 1 < bestLength) {                    bestLength = right - left + 1;                    bestStart = left;                }                char out = s.charAt(left);                need[out]++;                if (need[out] > 0) {                    missing++;                }                left++;            }        }        return bestLength == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLength);    }    public static void main(String[] args) {        System.out.println(minWindow("ADOBECODEBANC", "ABC"));        System.out.println(minWindow("a", "a"));        System.out.println("[" + minWindow("a", "aa") + "]");        System.out.println(minWindow("ab", "b"));        System.out.println(minWindow("aa", "aa"));    }}

BANCa[]baa

• Next: Prefix Sums and Difference Arrays handles range sums and subarray-sum problems that sliding windows cannot, including negative numbers.
• Related: Two Pointers for the underlying idea, and Hashing for the frequency maps used here.
• Practice habit: when you see "longest" or "shortest" together with "substring" or "subarray", write down what the window must remember, and how it changes when an element enters and when one leaves.