Advanced Sliding Window

1. Introduction: The Dynamic Caterpillar

You have already learned the basic Sliding Window: a fixed-size window (like $K=3$) that slides across an array. Advanced Sliding Window problems do not have a fixed size. The window is dynamic. It acts like a caterpillar—stretching its head forward as far as it can to consume valid elements, and then dragging its tail forward when it consumes too much and violates the rules.

This dynamic expansion and contraction allows us to solve complex "longest/shortest contiguous subarray" problems in $O(N)$ time instead of an $O(N^2)$ brute force.

2. Core Concept: The Shrink-Wrap Template

Every dynamic sliding window follows the exact same logical architecture:

1. Initialize left and right pointers to 0.
2. Expand the window by incrementing right and adding the new element to our state.
3. If the state becomes invalid, enter a while loop to shrink the window from the left until the state is valid again.
4. Once the state is valid, update our global maxLength (or minLength).

3. Advanced Code Example: Longest Substring with At Most K Distinct Characters

Problem Statement: (LeetCode 340) Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

The Insight: Our "state" is the number of distinct characters in our window. We can track this using a HashMap Map<Character, Integer> frequency.

• Expansion: We add s.charAt(right) to the map.
• Violation: The window is invalid when map.size() > k.
• Contraction: We decrement the frequency of s.charAt(left). If the frequency hits 0, we MUST remove it from the map completely to reduce map.size(). Then we increment left.

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return 0;
        
        Map<Character, Integer> windowCounts = new HashMap<>();
        int left = 0, maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            // 1. Expand
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
            
            // 2. Shrink if invalid
            while (windowCounts.size() > k) {
                char leftChar = s.charAt(left);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                
                // CRITICAL: Remove the key if count hits 0 to accurately track distinct characters
                if (windowCounts.get(leftChar) == 0) {
                    windowCounts.remove(leftChar);
                }
                left++;
            }
            
            // 3. Update Answer (Window is guaranteed valid here)
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

4. Advanced Code Example: Minimum Window Substring

Problem Statement: (LeetCode 76) Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

This is universally considered one of the hardest Sliding Window problems. The Insight: Our target is a frequency map of t. Our window state is a frequency map of s. We expand until our window map has $\ge$ counts for every character in the target map. Once valid, we record the length, and then we actively TRY to break it by shrinking from the left! The moment we break it, we stop shrinking, record the left pointer's new position, and go back to expanding right.

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";

        // 1. Target Map
        Map<Character, Integer> targetCounts = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetCounts.put(c, targetCounts.getOrDefault(c, 0) + 1);
        }

        // requiredChars is the number of UNIQUE characters we need to match
        int requiredChars = targetCounts.size(); 
        
        int left = 0, right = 0;
        int matchedChars = 0; // Tracks how many unique characters have met the required frequency
        
        Map<Character, Integer> windowCounts = new HashMap<>();
        
        // Output tracking variables
        int minLength = Integer.MAX_VALUE;
        int bestLeft = 0, bestRight = 0;

        while (right < s.length()) {
            // EXPAND
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            // If this character's frequency perfectly matches the target, we increment our match count
            if (targetCounts.containsKey(c) && 
                windowCounts.get(c).intValue() == targetCounts.get(c).intValue()) {
                matchedChars++;
            }

            // SHRINK: If the window is perfectly valid, try to squeeze it smaller!
            while (matchedChars == requiredChars) {
                // Update minimums
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    bestLeft = left;
                    bestRight = right;
                }

                // Pop the left character
                char leftChar = s.charAt(left);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                
                // If popping this character broke the target frequency, we lose a matchedChar!
                if (targetCounts.containsKey(leftChar) && 
                    windowCounts.get(leftChar).intValue() < targetCounts.get(leftChar).intValue()) {
                    matchedChars--;
                }
                
                left++;
            }
            right++;
        }

        return minLength == Integer.MAX_VALUE ? "" : s.substring(bestLeft, bestRight + 1);
    }
}

5. The "Exact K" Math Trick

What if a problem asks for Exactly K instead of At Most K? e.g., "Subarrays with exactly K different integers" (LeetCode 992).

The Insight: A sliding window cannot directly compute "Exactly K". Why? Because if the window is valid at size 5, and we expand it to size 6, it might STILL be valid (if the new character is a duplicate). We don't know when to shrink!

The Math Trick: $Exactly(K) = AtMost(K) - AtMost(K-1)$ You write the standard AtMost(K) sliding window algorithm, and you just call it twice!

6. Common Mistakes Beginners Make

1. Comparing Integer objects with ==

   • The Mistake: if (window.get(c) == target.get(c))
   • Why it's wrong: Java caches integers from -128 to 127. If the string is massive and the character count hits 200, == compares the memory addresses of two different Integer objects and evaluates to false, even if both values are 200!
   • The Fix: Always use .equals() or .intValue() == .intValue() when comparing wrapper classes.

2. Failing to clean up the HashMap

   • The Mistake: map.put(c, map.get(c) - 1) without removing the key when it hits 0.
   • Why it's wrong: If you use map.size() to check how many distinct characters are in your window, a key with a value of 0 still counts towards the map's size! You must explicitly call map.remove(c).

3. Using Sliding Window for Subarrays with Negative Numbers

   • The Mistake: Trying to find the longest subarray summing to $K$ when the array contains negatives.
   • Why it's wrong: Sliding window relies on a monotonic property: expanding the window ALWAYS increases the sum, and shrinking ALWAYS decreases it. If you have negative numbers, expanding might decrease the sum! The logic collapses. (Use Prefix Sum Hashing instead).

7. Interview Q&A

Q1: How do you optimize the space complexity if the string only contains ASCII characters? Answer: Instead of a HashMap, use an int[128] array. The character itself acts as the index (counts[c]++). This drops the space complexity from $O(V)$ auxiliary object overhead to a strict $O(1)$ constant 128 bytes.

Q2: What is the "Sliding Window Maximum"? Answer: That is a totally different pattern involving a Monotonic Deque, not a standard two-pointer window. It requires mathematically purging smaller elements from the queue as the window slides.

8. Practice Problems

1. Longest Repeating Character Replacement (LeetCode 424)
   • Goal: The window is invalid if windowLength - maxFrequencyInWindow > k.
2. Subarrays with K Different Integers (LeetCode 992 - Hard)
   • Goal: Master the Exactly(K) = AtMost(K) - AtMost(K-1) trick.
3. Minimum Window Substring (LeetCode 76 - Hard)
   • Goal: Master the target frequency matching logic.

9. Summary

• The Template: for(right = 0...) { add; while(invalid) { remove; left++; } update max; }
• Monotonicity: Dynamic sliding windows ONLY work if expanding makes the window "more invalid" and shrinking makes it "more valid".
• The Exactly K Trick: Execute AtMost(K) - AtMost(K-1).

Advanced Code Implementations

// Example: Longest Substring with At Most K Distinct Characters
import java.util.*;

public class LongestSubstringKDistinct {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return 0;
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c, 0) + 1);
            
            while (map.size() > k) {
                char leftChar = s.charAt(left);
                map.put(leftChar, map.get(leftChar) - 1);
                if (map.get(leftChar) == 0) {
                    map.remove(leftChar);
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

// Example: Permutation in String
public class PermutationInString {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] s1map = new int[26];
        int[] s2map = new int[26];
        
        for (int i = 0; i < s1.length(); i++) {
            s1map[s1.charAt(i) - 'a']++;
            s2map[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (matches(s1map, s2map)) return true;
            s2map[s2.charAt(i + s1.length()) - 'a']++;
            s2map[s2.charAt(i) - 'a']--;
        }
        return matches(s1map, s2map);
    }
    
    private boolean matches(int[] s1map, int[] s2map) {
        for (int i = 0; i < 26; i++) {
            if (s1map[i] != s2map[i]) return false;
        }
        return true;
    }
}

Expanded Interview Q&A

Q1: How do you identify when to use a variable vs fixed sliding window?

Answer: A fixed window is used when the problem specifies a specific size (e.g., "substring of length k"). Variable windows are used for dynamic conditions (e.g., "sum is exactly k" or "at most k distinct").

Q2: What is the main advantage of the sliding window technique?

Answer: It reduces the time complexity of nested loop brute-force solutions from O(N^2) or O(N^3) down to O(N).

Q3: In variable sliding windows, when do you shrink the window?

Answer: You shrink the window from the left when the window becomes "invalid" according to the problem constraints.

Q4: Can sliding window be used with negative numbers for finding a target sum?

Answer: No. If elements are negative, adding an element doesn't guarantee the sum increases. You must use prefix sums with a HashMap instead.

Q5: Why use an array instead of a HashMap for character counts in Permutation in String?

Answer: An array of size 26 is much faster to allocate and access, avoiding hashing overhead when the character set is restricted to lowercase English letters.