Sliding Window

Instead of checking every possible subarray with nested loops, a sliding window moves two boundaries through the array, expanding and shrinking to find the optimal range in O(n).

• Replaces O(n²) brute force (all subarray pairs) with O(n) by reusing work from the previous window
• Two modes: maximum/longest (shrink while invalid, update after) and minimum/shortest (shrink while valid, update before)
• Reach for it when the problem asks for an optimal contiguous subarray or substring with a condition on its contents.

Practice Tips

How to Identify a Sliding Window Problem

• Problem asks for longest, shortest, maximum, or minimum subarray or substring
• The subarray must be contiguous — no skipping elements
• There is a validity condition on the window contents (sum, distinct count, char frequency)
• A brute force solution would use nested loops over subarrays

Sliding Window vs. Other Techniques

Interview Approach

1. Ask: Is the window variable-size or fixed-size?
2. Ask: Am I maximizing or minimizing?
3. Identify: What makes the window valid or invalid?
4. Identify: How do I track window state — running sum, HashMap, count?
5. Watch for: Off-by-one when checking window size, updating result at the right moment

3 Main Patterns

Pattern 1: Maximum/Longest

Copy// Expand right, shrink while INVALID, update result AFTER shrinking
for (int right = 0; right < n; right++) {
    addToWindow(right);
    while (invalid()) {
        removeFromWindow(left++);
    }
    maxResult = Math.max(maxResult, right - left + 1); // update AFTER
}

Pattern 2: Minimum/Shortest

Copy// Expand right, shrink while VALID, update result BEFORE shrinking
for (int right = 0; right < n; right++) {
    addToWindow(right);
    while (valid()) {
        minResult = Math.min(minResult, right - left + 1); // update BEFORE
        removeFromWindow(left++);
    }
}

Pattern 3: Fixed-size

Copy// Window is exactly k elements — slide by evicting left when window exceeds k
for (int right = 0; right < n; right++) {
    addToWindow(right);
    while (right - left + 1 >= k) {
        checkOrUpdateResult();
        removeFromWindow(left++);
    }
}

General Templates

Variable-size Template

Copypublic int slidingWindow(int[] nums) {
    int left = 0;
    int result = 0;                            // or Integer.MAX_VALUE for minimum
    Map<Integer, Integer> window = new HashMap<>();

    for (int right = 0; right < nums.length; right++) {
        // 1. Expand: add right element to window
        window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);

        // 2. Shrink while condition is violated (max) or satisfied (min)
        while (/* window invalid for max, or window valid for min */) {
            // For MINIMUM: update result here, before removing left
            // result = Math.min(result, right - left + 1);

            int leftVal = nums[left];
            left++;
            window.put(leftVal, window.get(leftVal) - 1);
            if (window.get(leftVal) == 0) {
                window.remove(leftVal);
            }
        }

        // 3. For MAXIMUM: update result here, after shrinking
        // result = Math.max(result, right - left + 1);
    }
    return result;
}

Fixed-size Template (Anagram / Permutation)

Copypublic void fixedWindow(String s, String p) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : p.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, valid = 0;

    for (int right = 0; right < s.length(); right++) {
        // 1. Expand
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        // 2. Slide: shrink when window hits target size
        while (right - left + 1 >= p.length()) {
            if (valid == need.size()) {
                /* found a match */
            }

            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
}

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of sliding window patterns.

Problem 1: Longest Substring Without Repeating Characters ⭐ MUST DO [B75-3]

Find the length of the longest substring with no repeated characters.

Example:

CopyInput:  s = "abcabcbb"
Output: 3   (substring "abc")

Input:  s = "pwwkew"
Output: 3   (substring "wke")

Solution:

Copypublic int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);

        // Shrink while INVALID: duplicate character in window
        while (window.get(c) > 1) {
            char leftChar = s.charAt(left);
            left++;
            window.put(leftChar, window.get(leftChar) - 1);
        }

        // Update AFTER shrinking (maximum pattern)
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

Complexity:

Real World: Session token validation in auth systems — find the longest sequence of unique request tokens before a duplicate appears (which signals a replay attack). Also used in network packet analysis to find the longest run of unique packet IDs in a stream before a collision.

Variations:

1. Longest substring with at most k repeating characters — change the invalidity condition from count > 1 to count > k. The window map and shrink logic stay identical.
2. Longest subarray with all distinct integers — same algorithm on an int array with a HashMap instead of a character map. Direct structural transfer.

Interview Disguises:

• "A network stream receives packet IDs. Find the longest consecutive run of packets with no repeated ID before a duplicate forces a buffer reset." — longest substring without repeating characters; packet IDs are the characters.
• "A music app tracks songs played in order. Find the longest streak of songs with no repeat — the user's longest 'no-repeat' listening session." — same max window with a uniqueness constraint; song IDs are the characters.

Problem 2: Minimum Size Subarray Sum

Find the minimum length subarray whose sum is greater than or equal to target. Return 0 if none exists.

Example:

CopyInput:  target = 7, nums = [2,3,1,2,4,3]
Output: 2   (subarray [4,3])

Input:  target = 4, nums = [1,4,4]
Output: 1   (subarray [4])

Key Insight:

• This is the minimum pattern: shrink while the window is valid (sum ≥ target), update result before shrinking.
• Using a running sum instead of a HashMap because all values are positive integers.

Solution:

Copypublic int minSubArrayLen(int target, int[] nums) {
    int left = 0, windowSum = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right];

        // Shrink while VALID: sum meets the target
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1); // update BEFORE
            windowSum -= nums[left];
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Complexity:

Real World: Warehouse shipping — finding the smallest contiguous batch of items on a conveyor belt whose combined weight meets a minimum shipping threshold. Also used in payment processing to find the fewest consecutive transactions that together clear a required balance.

Variations:

1. Minimum window with product ≥ target — replace the running sum with a running product; shrink while product >= target. Watch for zeros (they collapse the product instantly).
2. Count subarrays with sum ≥ target — instead of tracking the minimum length, count all valid windows. Requires a different approach (prefix sums + binary search) since you can't stop at the first valid window.

Interview Disguises:

• "A warehouse conveyor belt has items with known weights. Find the smallest contiguous group of items whose total weight meets the minimum load for a truck shipment." — minimum size subarray sum; item weights are the array, truck minimum is the target.
• "A fundraiser receives donations in the order they arrive. Find the fewest consecutive donations that together hit the campaign's funding goal." — same shrink-while-valid minimum pattern; donation amounts are the array.

Problem 3: Longest Substring with K Distinct Characters

Find the length of the longest substring that contains at most k distinct characters.

Example:

CopyInput:  s = "eceba", k = 2
Output: 3   (substring "ece")

Input:  s = "aa", k = 1
Output: 2   (substring "aa")

Key Insight:

• Invalidity condition is simply window.size() > k — the map size directly tells you distinct character count.
• "At most k distinct" means 0 through k are all valid. The window only shrinks when you hit k+1.

Solution:

Copypublic int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);

        // Shrink while INVALID: more than k distinct chars
        while (window.size() > k) {
            char leftChar = s.charAt(left);
            left++;
            window.put(leftChar, window.get(leftChar) - 1);
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }
        }

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

    return maxLen;
}

Complexity:

Real World: Streaming analytics — finding the longest uninterrupted segment of a server log that involves at most k distinct event types, used to identify the longest stable operational period before too many anomaly types appear. Also used in genomics to find the longest DNA segment with at most k distinct bases.

Variations:

1. Exactly k distinct characters — longest with exactly k = (longest with ≤ k) minus (longest with ≤ k-1). Run the same function twice with different limits and subtract.
2. Longest subarray with at most k distinct integers — same algorithm on an int array with an Integer HashMap. The window map and shrink condition are identical; only the input type changes.

Interview Disguises:

• "A server log streams event type codes. Find the longest uninterrupted sequence of events that involves at most 2 distinct event categories before operations become too varied to analyze." — k distinct with k=2; this is Fruit Into Baskets in disguise, which is itself this problem in disguise.
• "A portfolio manager can hold at most k different stocks simultaneously. Given a sequence of daily trades, find the longest continuous trading streak without exceeding k active positions." — at most k distinct values in a contiguous window = this problem exactly.

Problem 4: Find All Anagrams in a String

Find all starting indices of anagrams of p in s.

Example:

CopyInput:  s = "cbaebabacd", p = "abc"
Output: [0, 6]   (substrings "cba" and "bac" are anagrams of "abc")

Input:  s = "abab", p = "ab"
Output: [0, 1, 2]

Key Insight:

• Fixed window of exactly p.length(). Use a valid counter to avoid comparing full maps — valid equals need.size() only when every required character has enough frequency in the window.
• An anagram is just a permutation — order doesn't matter, only counts.

Solution:

Copypublic List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : p.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, valid = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        // Slide: shrink when window reaches target size
        while (right - left + 1 >= p.length()) {
            if (valid == need.size()) {
                result.add(left);
            }

            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }

    return result;
}

Complexity:

Real World: Plagiarism detection — scanning a document for every position where the same words as a target phrase appear regardless of order. Also used in genomics to find all positions in a genome where a target gene's base pairs appear in any arrangement.

Variations:

1. Permutation in String — identical algorithm; return a boolean on the first match instead of collecting all indices. If you can solve this problem, permutation check is a 2-minute change.
2. Minimum window anagram — find the shortest window containing all characters of p (not necessarily a fixed-size window). This transitions from fixed-size to the minimum pattern used in Minimum Window Substring.

Interview Disguises:

• "A plagiarism detector scans a document and flags every position where the same set of words as a reference phrase appears, regardless of word order." — find all anagrams; words are the characters, phrase length is the fixed window size.
• "A genomics tool searches a long DNA sequence for every position where a target gene's bases appear in any order — a scrambled match still counts as a hit." — fixed-size window sliding over a sequence, checking character frequency match = find all anagrams.

Problem 5: Longest Repeating Character Replacement ⭐ MUST DO [B75-424]

Find the length of the longest substring containing the same letter after replacing at most k characters.

Example:

CopyInput:  s = "ABAB", k = 2
Output: 4   (replace both B's with A to get "AAAA")

Input:  s = "AABABBA", k = 1
Output: 4   (replace one B to get "AABAA" or "AAABBA")

Key Insight:

• windowSize - maxCount tells you the minimum replacements needed. If this exceeds k, the window is invalid.
• maxCount only ever increases — you never need to recalculate it when shrinking. When the window shrinks, maxCount may be stale but it won't let an invalid window pass (it errs on the side of keeping the window too large, which is fine for a maximum problem).

Solution:

Copypublic int characterReplacement(String s, int k) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, maxCount = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        maxCount = Math.max(maxCount, window.get(c));

        // Shrink while INVALID: replacements needed exceed k
        while (right - left + 1 - maxCount > k) {
            char leftChar = s.charAt(left);
            left++;
            window.put(leftChar, window.get(leftChar) - 1);
        }

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

    return maxLen;
}

Complexity:

Real World: Run-length encoding optimization — finding the longest substring that can be made into a single repeated character with at most k substitutions, to maximize compression ratio. Also used in quality control to find the longest production run that can be considered uniform after tolerating k defects.

Variations:

1. Max consecutive ones with k flips (LC 1004) — binary array version of this problem. Count 1s as maxCount; condition becomes windowSize - count1s > k. Same formula, simpler window state since there are only two values.
2. Minimum replacements to make entire string uniform — no window needed. Answer is n - maxFrequency(s). Recognizing when the sliding window reduces to a simpler formula is a good interview signal.

Interview Disguises:

• "A data compressor finds the longest substring it can turn into a single repeated character by changing at most k characters — longer uniform runs compress better with run-length encoding." — longest repeating character replacement verbatim; compression framing.
• "A network engineer wants the longest contiguous block of identical packet types, allowing at most k misclassified packets to be relabeled as the dominant type." — windowSize - maxCount > k is the invalidity condition; packet types are the characters.

Problem 6: Minimum Window Substring ⭐ MUST DO [B75-76]

Find the minimum window in s that contains all characters of t. Return empty string if none exists.

Example:

CopyInput:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Input:  s = "a", t = "a"
Output: "a"

Key Insight:

• Two maps: need (target frequencies from t) and window (current window frequencies).
• valid counter tracks how many distinct characters in need are fully satisfied in window. Only increments when window.get(c) == need.get(c) — not on every addition.
• Minimum pattern: shrink while valid (all characters covered), update result before shrinking each time.

Solution:

Copypublic String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, valid = 0;
    int minLen = Integer.MAX_VALUE, minStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        // Shrink while VALID: window contains all required characters
        while (valid == need.size()) {
            // Update result BEFORE shrinking (minimum pattern)
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Complexity:

Real World: Search engine snippet generation — finding the shortest passage in a document that contains all of the user's search keywords, used to generate the most relevant excerpt to display in search results. Also used in legal discovery tools to find the smallest contract clause containing all required terms.

Variations:

1. Minimum window with exact frequencies — t may contain duplicate characters (e.g. t = "AA") meaning the window must contain at least 2 A's. This is already handled by the need map and valid counter — no code change needed; worth confirming you understand why.
2. Smallest range covering elements from k sorted lists — generalization of the same valid-counter idea: instead of characters from t, you need one element from each of k lists. Solved with a min-heap sliding window; the "all lists represented" check mirrors the valid == need.size() condition here.

Interview Disguises:

• "A search engine must highlight the shortest passage in a document that contains every one of the user's search terms at least once." — minimum window substring; terms are the characters of t, document is s.
• "A legal discovery tool scans contracts and must flag the shortest clause that contains all required legal terms from a compliance checklist." — same two-map valid-counter minimum pattern; legal terms are t, contract text is s.

Quick Reference Table

When to Use Each Pattern

Maximum/Longest

• Problem says "longest" or "maximum length" subarray or substring
• There is a condition that can become violated as the window grows
• Examples: no repeating chars, at most k distinct, at most k replacements

Minimum/Shortest

• Problem says "shortest" or "minimum length" subarray
• There is a condition that must be satisfied — you shrink while you still have it
• Examples: sum ≥ target, contains all chars of t

Fixed-size

• Window size is given (e.g. exactly k elements, or exactly p.length())
• You slide by evicting left whenever the window hits the target size
• Examples: anagrams, permutation check

Common Mistakes to Avoid

General Sliding Window Mistakes

1. Updating result at the wrong time — maximum problems update after shrinking, minimum problems update before. Swapping these gives wrong answers.
2. Not removing entries from the map when count reaches 0 — leaves stale keys in the window map, corrupting window.size() checks.
3. Using if instead of while to shrink — if the window needs to shrink by more than one step, an if only removes one element and leaves an invalid window.

Maximum Pattern Mistakes

4. Forgetting window.size() > k evicts only one entry per step — the while loop handles this correctly, but switching to if breaks it.
5. Not tracking maxCount correctly in Problem 7 — maxCount should only be updated when expanding, not recalculated during shrinking.

Minimum Pattern Mistakes

6. Checking result after shrinking — for minimum problems, the result must be captured before the window is shrunk, not after.
7. Forgetting to decrement valid when removing a character — if you remove the char before checking whether it was fully satisfied, valid becomes permanently wrong.

Fixed-size Pattern Mistakes

8. Checking result after removing left — for anagram/permutation, check the result before evicting the left character from the window.