Sliding Window Pattern¶

Overview¶

Maintain a "window" over a portion of data that slides through to find optimal subarrays/substrings satisfying certain conditions.

When to Use¶

Find max/min subarray of size K
Longest/shortest substring with specific property
Subarray with given sum
String permutation/anagram problems
Contiguous sequence problems

Sliding Window Step-by-Step

Window Types: - Fixed Window: Maintain exact size K, slide by adding right and removing left - Variable Window: Expand right to grow, contract left when invalid

Template Code¶

Fixed Size Window - Max Sum of K Elements¶

public int maxSumSubarray(int[] nums, int k) {
    int windowSum = 0;
    int maxSum = Integer.MIN_VALUE;

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

        if (i >= k - 1) {  // Window is full
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= nums[i - k + 1];  // Remove left element
        }
    }
    return maxSum;
}

Variable Window - Minimum Size Subarray Sum¶

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLength = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];  // Expand window

        while (sum >= target) {  // Shrink while valid
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

Longest Substring Without Repeating Characters¶

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>();
    int maxLength = 0;
    int left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
            left = charIndex.get(c) + 1;  // Jump past duplicate
        }

        charIndex.put(c, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Longest Substring with K Distinct Characters¶

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> charCount = new HashMap<>();
    int maxLength = 0;
    int left = 0;

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

        while (charCount.size() > k) {  // Too many distinct
            char leftChar = s.charAt(left);
            charCount.put(leftChar, charCount.get(leftChar) - 1);
            if (charCount.get(leftChar) == 0) {
                charCount.remove(leftChar);
            }
            left++;
        }

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

Find All Anagrams in String¶

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

    int[] pCount = new int[26];
    int[] sCount = new int[26];

    // Count pattern characters
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }

    for (int i = 0; i < s.length(); i++) {
        sCount[s.charAt(i) - 'a']++;  // Add right

        if (i >= p.length()) {
            sCount[s.charAt(i - p.length()) - 'a']--;  // Remove left
        }

        if (i >= p.length() - 1 && Arrays.equals(pCount, sCount)) {
            result.add(i - p.length() + 1);
        }
    }
    return result;
}

Minimum Window Substring¶

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";

    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> have = new HashMap<>();

    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int required = need.size();
    int formed = 0;
    int left = 0;
    int minLen = Integer.MAX_VALUE;
    int minStart = 0;

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

        if (need.containsKey(c) && have.get(c).equals(need.get(c))) {
            formed++;
        }

        while (formed == required) {  // Valid window, try to shrink
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            char leftChar = s.charAt(left);
            have.put(leftChar, have.get(leftChar) - 1);

            if (need.containsKey(leftChar) &&
                have.get(leftChar) < need.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }

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

Sliding Window Maximum (with Deque)¶

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // Stores indices

    for (int i = 0; i < nums.length; i++) {
        // Remove elements outside window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // Remove smaller elements (they'll never be max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Time & Space Complexity¶

Problem	Time	Space
Fixed window max sum	O(n)	O(1)
Min subarray sum	O(n)	O(1)
Longest without repeat	O(n)	O(min(n,m))
K distinct chars	O(n)	O(k)
Find anagrams	O(n)	O(1)
Min window substring	O(n+m)	O(m)
Sliding window max	O(n)	O(k)

Common Interview Questions¶

Maximum Sum Subarray of Size K - Fixed window
Minimum Size Subarray Sum - Variable window ≥ target
Longest Substring Without Repeating Characters - Classic
Longest Substring with At Most K Distinct Characters - Variable
Fruit Into Baskets - Same as K=2 distinct
Permutation in String - Check if s2 contains permutation of s1
Find All Anagrams in a String - Return all start indices
Minimum Window Substring - Smallest window containing all chars
Sliding Window Maximum - Max in each window of size K
Substring with Concatenation of All Words - Complex anagram
Longest Repeating Character Replacement - With K replacements
Max Consecutive Ones III - With K flips allowed
Subarrays with K Different Integers - Exactly K distinct

Tips & Tricks¶

Fixed window: expand until size K, then slide (add right, remove left)
Variable window: expand right, contract left when invalid
Use HashMap for character frequency tracking
Use Deque for monotonic window (max/min in window)
"At most K" - "At most K-1" = "Exactly K" trick
Always track window state incrementally, don't recompute