Sliding Window

Back to DSA & Algorithms/00 - Roadmap Overview

What is Sliding Window?

Sliding window is a technique for processing contiguous subarrays/substrings. Instead of recalculating everything from scratch for each position, you "slide" a window across the data, adding one element on the right and removing one on the left.

Why It Works

Brute force: for every starting position, check every ending position → O(n²). Sliding window: maintain a running state as you expand/shrink → O(n).

The key: adjacent windows overlap massively. If you computed the answer for [i, j], the answer for [i, j+1] is just a small update.

The Two Types

TypeWindow SizeTemplate
Fixed-sizeKnown (given K)Slide window of exactly K elements
Variable-sizeUnknown (find it)Expand right, shrink left when invalid

Pattern 1: Fixed-Size Window

What it is

The window size is given (say K). Slide it across the array, maintaining a running computation.

When to use it

  • "Maximum sum of K consecutive elements"
  • "Average of every K-length subarray"
  • "Find all anagrams of a pattern in a string" (window size = pattern length)

The Mental Model

Imagine looking through a fixed-width picture frame that you slide along a mural. You see exactly K panels at a time. As you slide right:

  • A new panel enters on the right
  • An old panel exits on the left
  • You update your notes based on what entered and left

Step-by-Step

java
// Problem: Maximum sum of any K consecutive elements
// Input: [2, 1, 5, 1, 3, 2], K = 3
// Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
// Answer: 9

public int maxSumSubarrayK(int[] nums, int k) {
    // Step 1: Compute sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    int maxSum = windowSum;

    // Step 2: Slide the window
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i];       // Add new element (entering right)
        windowSum -= nums[i - k];   // Remove old element (exiting left)
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

// Walkthrough:
// Initial window [2,1,5]: sum = 8
// i=3: add nums[3]=1, remove nums[0]=2 → sum = 8+1-2 = 7
// i=4: add nums[4]=3, remove nums[1]=1 → sum = 7+3-1 = 9  ← new max!
// i=5: add nums[5]=2, remove nums[2]=5 → sum = 9+2-5 = 6
// Answer: 9

Problems

Pattern 2: Variable-Size Window (The Core Pattern)

What it is

You don't know the window size. You expand the window by moving the right pointer, and shrink it by moving the left pointer when some constraint is violated.

When to use it

  • "Longest substring/subarray satisfying some condition"
  • "Shortest substring/subarray satisfying some condition"
  • Signal words: contiguous, substring, subarray, window, at most K

The Mental Model

Imagine you're stretching a rubber band on a ruler:

  1. Stretch right (expand): keep going as long as the rubber band doesn't break (constraint holds)
  2. Release left (shrink): when the rubber band breaks (constraint violated), let go from the left until it's okay again
  3. Measure: after each adjustment, check if this is the longest rubber band you've seen

The Universal Template (Memorize This!)

java
public int slidingWindow(char[] sOrNums) {
    int left = 0;
    Map<Character, Integer> state = new HashMap<>(); // or counter, set, sum — whatever tracks your window
    int best = 0;    // or Integer.MAX_VALUE for "shortest"

    for (int right = 0; right < sOrNums.length; right++) {
        // ┌─────────────────────────────┐
        // │ STEP 1: EXPAND              │
        // │ Add s[right] to window state │
        // └─────────────────────────────┘
        updateStateWith(sOrNums[right]);

        // ┌─────────────────────────────┐
        // │ STEP 2: SHRINK              │
        // │ While window is INVALID,    │
        // │ remove s[left] from state   │
        // └─────────────────────────────┘
        while (windowIsInvalid()) {
            removeFromState(sOrNums[left]);
            left++;
        }

        // ┌─────────────────────────────┐
        // │ STEP 3: UPDATE ANSWER       │
        // │ Current window is valid,    │
        // │ so check if it's the best   │
        // └─────────────────────────────┘
        best = Math.max(best, right - left + 1);
    }

    return best;
}

Example 1: Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring with all unique characters.

java
// Input: "abcabcbb"
// Answer: 3 ("abc")

public int lengthOfLongestSubstring(String s) {
    Set<Character> charSet = new HashSet<>(); // Tracks characters in current window
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        // STEP 1: Try to add s.charAt(right)
        // STEP 2: If it already exists, shrink until it doesn't
        while (charSet.contains(s.charAt(right))) {
            charSet.remove(s.charAt(left));
            left++;
        }

        // Now s.charAt(right) is not in the set — safe to add
        charSet.add(s.charAt(right));

        // STEP 3: Update answer
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

// Walkthrough: "abcabcbb"
//
// right=0 'a': set={a}, window="a", len=1
// right=1 'b': set={a,b}, window="ab", len=2
// right=2 'c': set={a,b,c}, window="abc", len=3  ← max so far
// right=3 'a': 'a' already in set!
//   remove 'a', left=1 → set={b,c}
//   add 'a' → set={b,c,a}, window="bca", len=3
// right=4 'b': 'b' already in set!
//   remove 'b', left=2 → set={c,a}
//   add 'b' → set={c,a,b}, window="cab", len=3
// right=5 'c': 'c' already in set!
//   remove 'c', left=3 → set={a,b}
//   add 'c' → set={a,b,c}, window="abc", len=3
// right=6 'b': 'b' already in set!
//   remove 'a', left=4 → set={b,c}. Still has 'b'!
//   remove 'b', left=5 → set={c}
//   add 'b' → set={c,b}, window="cb", len=2
// right=7 'b': 'b' already in set!
//   remove 'c', left=6 → set={b}. Still has 'b'!
//   remove 'b', left=7 → set={}
//   add 'b' → set={b}, window="b", len=1
//
// Answer: 3

Example 2: Longest Repeating Character Replacement

Problem: You can replace at most K characters. Find the longest substring with all same characters after replacements.

Key insight: A window is valid if window_length - count_of_most_frequent_char <= k. The "replacements needed" is every character that ISN'T the most frequent one.

java
public int characterReplacement(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>(); // Character frequencies in current window
    int left = 0;
    int maxFreq = 0;  // Count of most frequent character in window
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        // EXPAND: Add s.charAt(right)
        freq.merge(s.charAt(right), 1, Integer::sum);
        maxFreq = Math.max(maxFreq, freq.get(s.charAt(right)));

        // SHRINK: If we need more than K replacements
        // Window size - most frequent = characters to replace
        while ((right - left + 1) - maxFreq > k) {
            freq.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }

        // UPDATE
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

// Example: s = "AABABBA", k = 1
// "AABA" → 4 chars, most_freq=3('A'), need 1 replacement → valid! length=4

Problems

Pattern 3: Shortest/Minimum Window (Shrink When Valid)

What it is

This is the reverse of Pattern 2. Instead of shrinking when invalid, you shrink when valid — because you want the smallest valid window.

When to use it

  • "Shortest subarray satisfying condition"
  • "Minimum window containing all characters"

The Key Difference

LONGEST (Pattern 2):
  - Expand right always
  - Shrink left when INVALID
  - Update answer AFTER shrinking (window is now valid)

SHORTEST (Pattern 3):
  - Expand right always
  - Shrink left when VALID (try to make window smaller)
  - Update answer BEFORE or DURING shrinking (window is valid)

Example: Minimum Window Substring

Problem: Find the smallest substring of s that contains all characters of t.

java
public String minWindow(String s, String t) {
    if (t.isEmpty() || s.isEmpty()) {
        return "";
    }

    // Count what we need
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.merge(c, 1, Integer::sum);   // e.g. {'A': 1, 'B': 1, 'C': 1}
    }
    int missing = t.length();              // Total characters still needed: 3

    int left = 0;
    int bestStart = 0;
    int bestLen = Integer.MAX_VALUE;

    for (int right = 0; right < s.length(); right++) {
        // EXPAND: Add s.charAt(right) to window
        char rc = s.charAt(right);
        if (need.getOrDefault(rc, 0) > 0) {
            missing--;                      // This character was actually needed
        }
        need.merge(rc, -1, Integer::sum);  // Decrement (can go negative = "extra")

        // SHRINK: While window is VALID (has everything), try smaller
        while (missing == 0) {
            // Update best answer
            int windowLen = right - left + 1;
            if (windowLen < bestLen) {
                bestStart = left;
                bestLen = windowLen;
            }

            // Try removing from left
            char lc = s.charAt(left);
            need.merge(lc, 1, Integer::sum);
            if (need.get(lc) > 0) {
                missing++;                  // We lost a needed character
            }
            left++;
        }
    }

    return bestLen != Integer.MAX_VALUE ? s.substring(bestStart, bestStart + bestLen) : "";
}

// Walkthrough: s = "ADOBECODEBANC", t = "ABC"
//
// We need: A:1, B:1, C:1 (missing=3)
//
// right=0 'A': need['A']=1>0 → missing=2. need={'A':0,'B':1,'C':1}
// right=1 'D': need['D']=0, not needed. missing=2
// right=2 'O': not needed. missing=2
// right=3 'B': need['B']=1>0 → missing=1. need={'A':0,'B':0,'C':1}
// right=4 'E': not needed. missing=1
// right=5 'C': need['C']=1>0 → missing=0! Window "ADOBEC" contains all!
//   Shrink:
//   best = "ADOBEC" (len=6)
//   remove 'A': need['A']=1>0 → missing=1. left=1. Stop shrinking.
//
// ... continue expanding and shrinking ...
// Eventually find "BANC" (len=4) as the smallest window.

Why the missing Counter?

Without missing, you'd have to check ALL values in need every time to see if the window is valid. That's O(26) for lowercase letters, or O(size of t) in general. The missing counter gives you an O(1) validity check.

Problems

Pattern 4: Window with Frequency Match

What it is

Check if a window's character frequencies match a target pattern. Used for anagram/permutation detection.

The Mental Model

You're playing Scrabble. You have a set of tiles (the pattern). You slide a window across the board and check: "Can I spell my word using exactly the letters in this window?"

Step-by-Step

java
// Problem: Find all start indices of anagrams of p in s
// Input: s = "cbaebabacd", p = "abc"
// Output: [0, 6] → "cba" at 0, "bac" at 6

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) {
        return result;
    }

    int[] pCount = new int[26];            // Target: a:1, b:1, c:1
    int[] window = new int[26];            // First window
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }
    for (int i = 0; i < p.length(); i++) {
        window[s.charAt(i) - 'a']++;
    }

    if (Arrays.equals(window, pCount)) {
        result.add(0);
    }

    // Slide the window
    for (int i = p.length(); i < s.length(); i++) {
        // Add new character (entering right)
        window[s.charAt(i) - 'a']++;

        // Remove old character (exiting left)
        window[s.charAt(i - p.length()) - 'a']--;

        // Check if current window matches
        if (Arrays.equals(window, pCount)) {
            result.add(i - p.length() + 1);
        }
    }

    return result;
}

Optimized Version (Avoid Comparing Entire Arrays)

java
public List<Integer> findAnagramsFast(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) {
        return result;
    }

    Map<Character, Integer> pCount = new HashMap<>();
    for (char c : p.toCharArray()) {
        pCount.merge(c, 1, Integer::sum);
    }
    Map<Character, Integer> window = new HashMap<>();
    int matches = 0;                        // How many characters have correct count
    int required = pCount.size();           // Total unique characters needed

    for (int i = 0; i < s.length(); i++) {
        // Add s.charAt(i) to window
        char ch = s.charAt(i);
        window.merge(ch, 1, Integer::sum);
        if (pCount.containsKey(ch) && window.get(ch).equals(pCount.get(ch))) {
            matches++;
        } else if (pCount.containsKey(ch) && window.get(ch).equals(pCount.get(ch) + 1)) {
            matches--;                      // Was matching, now over-counted
        }

        // Remove leftmost if window too big
        if (i >= p.length()) {
            char old = s.charAt(i - p.length());
            if (pCount.containsKey(old) && window.get(old).equals(pCount.get(old))) {
                matches--;                  // Was matching, now under-counted
            } else if (pCount.containsKey(old) && window.get(old).equals(pCount.get(old) + 1)) {
                matches++;                  // Was over, now correct
            }
            window.merge(old, -1, Integer::sum);
        }

        // All characters match?
        if (matches == required) {
            result.add(i - p.length() + 1);
        }
    }

    return result;
}

Problems

Things You MUST Be Aware Of

1. Window Size = right - left + 1 (Not right - left)

Window [left=2, right=5] has elements at indices 2, 3, 4, 5
Size = 5 - 2 + 1 = 4 elements (not 3!)

2. When to Use while vs if for Shrinking

java
// WHILE: For variable-size windows (might need to shrink multiple times)
while (windowIsInvalid()) {
    left++;
}

// IF: Only when you know you shrink exactly once per expansion
// (rare — almost always use while)

3. Cleaning Up Frequency Maps

java
// When a character's count reaches 0, REMOVE it from the map
// Otherwise map comparison fails:
// {a=1, b=0} is NOT equal to {a=1}
if (freq.get(ch) == 0) {
    freq.remove(ch);
}

4. Empty String / Window Larger Than Input

java
// Always check: what if s is empty? What if k > nums.length?
if (s.isEmpty() || k > nums.length) {
    return defaultValue;
}

5. "At Most K" vs "Exactly K"

java
// "Exactly K distinct" = "At most K distinct" - "At most K-1 distinct"
// This is a powerful trick! Solve "at most K" (easier), then subtract.
public int exactlyK(int[] nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

6. Negative Numbers Break Sliding Window for Sums

java
// Sliding window for "shortest subarray with sum >= K" ONLY works
// if all numbers are positive (shrinking always decreases sum).
// With negative numbers, you need monotonic deque instead.

Decision Guide

Fixed window size given (K)?
  └── Fixed-size sliding window (Pattern 1)

"LONGEST substring/subarray with at most..."
  └── Variable window: expand always, shrink when INVALID (Pattern 2)

"SHORTEST substring/subarray containing all..."
  └── Variable window: expand always, shrink when VALID (Pattern 3)

"Find all anagrams/permutations in string"
  └── Fixed window (size = pattern length) + frequency match (Pattern 4)

"Exactly K distinct characters"
  └── atMost(K) - atMost(K-1) trick

Numbers can be negative?
  └── Sliding window might not work. Consider prefix sum + hash map instead.