Session-02-SlidingWindow

Practice Session 2: Sliding Window

Problem 1: Minimum Size Subarray Sum

Link: LeetCode 209

Quick Summary: Find minimal length of contiguous subarray with sum ≥ target.

Industry Context: Resource allocation (minimum resources needed), batch processing (optimal batch sizes)

Solutions

Approach 1: Brute Force

public int minSubArrayLen(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                minLen = Math.min(minLen, j - i + 1);
                break;
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

• Time: O(n²)
• Space: O(1)
• Tradeoff: Simple but slow

Approach 2: Sliding Window (Optimal)

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        
        // Shrink window while valid
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

• Time: O(n) - each element visited at most twice
• Space: O(1)
• Tradeoff: Optimal solution

---

Problem 2: Longest Repeating Character Replacement

Link: LeetCode 424

Quick Summary: Find longest substring with same character after k replacements.

Industry Context: Error correction codes, data compression, signal processing

Solutions

Approach 1: Sliding Window with Frequency Map

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, maxCount = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        maxCount = Math.max(maxCount, ++count[s.charAt(right) - 'A']);
        
        // If current window size - most frequent char > k, shrink
        while (right - left + 1 - maxCount > k) {
            count[s.charAt(left) - 'A']--;
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

• Time: O(n)
• Space: O(26) = O(1) for fixed alphabet
• Key Insight: Window is valid if (window_size - max_frequency) ≤ k

---

Problem 3: Permutation in String

Link: LeetCode 567

Quick Summary: Check if s2 contains permutation of s1 as substring.

Industry Context: Pattern matching in logs, DNA sequence analysis, intrusion detection

Solutions

Approach 1: Fixed Window with Frequency Match

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    
    int[] s1Count = new int[26];
    int[] s2Count = new int[26];
    
    for (int i = 0; i < s1.length(); i++) {
        s1Count[s1.charAt(i) - 'a']++;
        s2Count[s2.charAt(i) - 'a']++;
    }
    
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (s1Count[i] == s2Count[i]) matches++;
    }
    
    int left = 0;
    for (int right = s1.length(); right < s2.length(); right++) {
        if (matches == 26) return true;
        
        // Add right character
        int rightChar = s2.charAt(right) - 'a';
        s2Count[rightChar]++;
        if (s2Count[rightChar] == s1Count[rightChar]) {
            matches++;
        } else if (s2Count[rightChar] == s1Count[rightChar] + 1) {
            matches--;
        }
        
        // Remove left character
        int leftChar = s2.charAt(left) - 'a';
        s2Count[leftChar]--;
        if (s2Count[leftChar] == s1Count[leftChar]) {
            matches++;
        } else if (s2Count[leftChar] == s1Count[leftChar] - 1) {
            matches--;
        }
        left++;
    }
    return matches == 26;
}

• Time: O(n) where n = s2.length
• Space: O(1) - fixed size arrays
• Optimization: Track matches instead of comparing arrays each time

Approach 2: Simpler Fixed Window

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    
    int[] count = new int[26];
    for (char c : s1.toCharArray()) {
        count[c - 'a']++;
    }
    
    int required = s1.length();
    int left = 0;
    
    for (int right = 0; right < s2.length(); right++) {
        // Expand window
        if (count[s2.charAt(right) - 'a']-- > 0) {
            required--;
        }
        
        // Check if window is valid
        if (required == 0) return true;
        
        // Shrink window
        if (right - left + 1 == s1.length()) {
            if (count[s2.charAt(left) - 'a']++ >= 0) {
                required++;
            }
            left++;
        }
    }
    return false;
}

• Time: O(n)
• Space: O(1)
• Tradeoff: Simpler logic, slightly less intuitive

---

Problem 4: Max Consecutive Ones III

Link: LeetCode 1004

Quick Summary: Maximum consecutive 1s after flipping at most k zeros.

Industry Context: Availability monitoring (max uptime with k failures), network reliability

Solution: Variable Sliding Window

public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;
    
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
        
        // Shrink window if too many zeros
        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

• Time: O(n)
• Space: O(1)
• Pattern: Same as “Longest Substring with At Most K Distinct Characters”

---

Java 21+ Feature: Pattern Matching for Switch

// Java 21+ - Enhanced switch for window type detection
public String analyzeWindow(int windowSize, int k) {
    return switch (windowSize) {
        case int s when s == k -> "Fixed window";
        case int s when s < k -> "Growing window";
        case int s when s > k -> "Shrinking window";
        default -> "Invalid window";
    };
}

---

Key Takeaways

1. Fixed Window: Size known upfront (average of k elements)
2. Variable Window: Expand until invalid, then shrink
3. Frequency Tracking: Use array for small alphabets, HashMap for large
4. Optimization: Track matches/requirements instead of full comparison
5. Template:

   int left = 0;
   for (int right = 0; right < n; right++) {
       // Add right element
       while (/* window invalid */) {
           // Remove left element
           left++;
       }
       // Update result
   }