Sliding Window: Template and Classic Problems

What is a Sliding Window?

The Sliding Window is an efficient technique for handling contiguous subarrays or substrings. By maintaining left and right pointers to define a window, it avoids the O(n²) complexity of nested loops, achieving O(n).

The Core Template:

int left = 0, right = 0;
while (right < n) {
    // 1. Expand the window (Move 'right' to include new content)
    window.add(s.charAt(right));
    right++;

    // 2. Shrink the window (When a condition is met or violated, move 'left')
    while (window needs to shrink) {
        window.remove(s.charAt(left));
        left++;
    }
    
    // 3. Update the answer
    res = Math.max(res, right - left);
}

Fixed-Length Window

Average of All Subarrays of Size K

double[] findAvgOfSubarrays(int[] arr, int k) {
    double[] result = new double[arr.length - k + 1];
    double windowSum = 0;
    for (int i = 0; i < arr.length; i++) {
        windowSum += arr[i];
        if (i >= k - 1) {
            result[i - k + 1] = windowSum / k;
            windowSum -= arr[i - k + 1];  // Slide out elements from the left
        }
    }
    return result;
}

Variable-Length Window

Longest Substring Without Repeating Characters (LeetCode 3)

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, res = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count.merge(c, 1, Integer::sum);   // Add to window
        while (count.get(c) > 1) {         // Duplicate found, shrink from the left
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
}

Minimum Size Subarray Sum (LeetCode 209, Sum ≥ target)

int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, res = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {   // Optimize window size once target is hit
            res = Math.min(res, right - left + 1);
            sum -= nums[left++];
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

Longest Substring with At Most K Distinct Characters

int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, res = 0;
    for (int right = 0; right < s.length(); right++) {
        count.merge(s.charAt(right), 1, Integer::sum);
        while (count.size() > k) {
            char lc = s.charAt(left);
            count.merge(lc, -1, Integer::sum);
            if (count.get(lc) == 0) count.remove(lc);
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
}

Problems Requiring Advanced State Tracking

Find All Anagrams in a String (LeetCode 438)

List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    for (int right = 0; right < s.length(); right++) {
        window[s.charAt(right) - 'a']++;
        if (right >= p.length())
            window[s.charAt(right - p.length()) - 'a']--;  // Fixed window sliding
        if (Arrays.equals(window, need))
            res.add(right - p.length() + 1);
    }
    return res;
}

Minimum Window Substring (LeetCode 76)

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

String minWindow(String s, String t) {
    int[] need = new int[128], have = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int left = 0, formed = 0, required = 0;
    for (int n : need) if (n > 0) required++;
    
    int currentFormed = 0;
    int resLen = Integer.MAX_VALUE, resStart = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        have[c]++;
        if (need[c] > 0 && have[c] == need[c]) currentFormed++;  // Requirement met for char 'c'
        
        while (currentFormed == required) {  // All requirements met, try to shrink
            if (right - left + 1 < resLen) {
                resLen = right - left + 1;
                resStart = left;
            }
            char lc = s.charAt(left);
            if (need[lc] > 0 && have[lc] == need[lc]) currentFormed--;
            have[lc]--;
            left++;
        }
    }
    return resLen == Integer.MAX_VALUE ? "" : s.substring(resStart, resStart + resLen);
}

Sliding Window vs. Prefix Sum

When is Sliding Window unusable? If an array contains negative numbers and you need to find a subarray sum equal to some value, the window lacks monotonicity (adding an element doesn't always increase the sum). In such cases, use Prefix Sum + Hash Map.