Dynamic Size Sliding Window Pattern

Overview

The Dynamic Size Sliding Window pattern is an advanced variation of the sliding window technique where the window size can grow or shrink based on certain conditions. Unlike fixed-size windows, dynamic windows adjust their boundaries to find optimal subarrays or substrings that satisfy given constraints. This flexibility makes it particularly powerful for solving problems where the optimal solution length isn't known beforehand.

When to Use This Pattern

• Variable Length Subarrays: Finding subarrays that meet specific criteria
• Substring Problems: Finding longest/shortest substrings with constraints
• Optimization Problems: Minimizing/maximizing window size under conditions
• Constraint-based Problems: Finding windows that satisfy given constraints
• Two-Pointer Variations: When both window boundaries need adjustment
• Cumulative Calculations: When running sums/products need tracking
• Character Frequency: Managing character counts in strings
• Subarray Properties: Checking dynamic range conditions
• Target Sum Problems: Finding variable-length subarrays with sum conditions
• Optimization with Constraints: Balancing multiple conditions

Key Characteristics

• Variable Window Size: Window length changes based on conditions
• Two-Pointer Technique: Often uses two pointers for window boundaries
• Dynamic Adjustment: Window expands/contracts based on criteria
• Optimization Focus: Finds optimal window size for conditions
• State Tracking: Maintains window state during adjustments

Real-World Applications

• Network Traffic Analysis: Variable time window monitoring
• Stock Market Analysis: Dynamic period trend detection
• Text Processing: Finding optimal substring matches
• Resource Allocation: Dynamic resource window management
• Stream Processing: Variable chunk size analysis

Why Dynamic Size Sliding Window Matters

• Flexibility: Adapts to varying conditions and constraints
• Optimization: Finds optimal subarray sizes automatically
• Efficiency: Maintains linear time complexity despite variable size
• Versatility: Solves complex substring and subarray problems

Let's explore how the dynamic size sliding window technique works visually and then dive into different programming language implementations.

Visual Demonstration

Dynamic window adjusting its size based on array elements

This animation demonstrates how a dynamic sliding window operates on an array. Notice how the window (highlighted in blue) dynamically adjusts its size while sliding through the array. The window can expand or contract based on certain conditions, making it ideal for problems like finding subarrays with specific properties.

Implementation Examples

C++

// Longest Substring Without Repeating Characters
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> charIndex(128, -1);
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            if (charIndex[s[end]] >= start) {
                start = charIndex[s[end]] + 1;
            }
            charIndex[s[end]] = end;
            maxLength = max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
};

// Minimum Size Subarray Sum
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLength = INT_MAX;
        int start = 0;
        int sum = 0;
        
        for (int end = 0; end < nums.size(); end++) {
            sum += nums[end];
            
            while (sum >= target) {
                minLength = min(minLength, end - start + 1);
                sum -= nums[start];
                start++;
            }
        }
        
        return minLength == INT_MAX ? 0 : minLength;
    }
};

Java

// Longest Substring Without Repeating Characters
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (charIndex.containsKey(c)) {
                start = Math.max(start, charIndex.get(c) + 1);
            }
            charIndex.put(c, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

// Minimum Size Subarray Sum
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int start = 0;
        int sum = 0;
        
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];
            
            while (sum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                sum -= nums[start];
                start++;
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

Python

# Longest Substring Without Repeating Characters
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {}
        max_length = 0
        start = 0
        
        for end, char in enumerate(s):
            if char in char_index and char_index[char] >= start:
                start = char_index[char] + 1
            char_index[char] = end
            max_length = max(max_length, end - start + 1)
        
        return max_length

# Minimum Size Subarray Sum
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_length = float('inf')
        start = 0
        curr_sum = 0
        
        for end in range(len(nums)):
            curr_sum += nums[end]
            
            while curr_sum >= target:
                min_length = min(min_length, end - start + 1)
                curr_sum -= nums[start]
                start += 1
        
        return min_length if min_length != float('inf') else 0

Common Patterns and Their Complexities

Pattern	Description	Time Complexity	Space Complexity
Substring Search	Find substrings meeting criteria	O(n)	O(k)
Target Sum	Find subarrays with sum conditions	O(n)	O(1)
Character Frequency	Track character counts	O(n)	O(k)
Two-Pointer Sliding	Adjust both window boundaries	O(n)	O(1)
State Management	Track window state variables	O(n)	O(k)

Practice Problems

Medium Level

1. Longest Substring Without Repeating Characters

   • Find longest substring with unique characters
   • Time: O(n), Space: O(k)

2. Longest Repeating Character Replacement

   • Find longest substring after k character replacements
   • Time: O(n), Space: O(1)

3. Minimum Size Subarray Sum

   • Find shortest subarray with sum ≥ target
   • Time: O(n), Space: O(1)

4. Max Consecutive Ones III

   • Find longest sequence after flipping k zeros
   • Time: O(n), Space: O(1)

5. Fruit Into Baskets

   • Maximum fruits from two types
   • Time: O(n), Space: O(1)

6. Subarray Product Less Than K

   • Count subarrays with product less than k
   • Time: O(n), Space: O(1)

7. Maximum Number of Occurrences of a Substring

   • Find most frequent substring with constraints
   • Time: O(n), Space: O(k)

8. Count Number of Nice Subarrays

   • Count subarrays with k odd numbers
   • Time: O(n), Space: O(1)

Hard Level

1. Minimum Window Substring

   • Find smallest window containing all characters
   • Time: O(n), Space: O(k)

2. Substring with Concatenation of All Words

   • Find substrings containing all words
   • Time: O(n*k), Space: O(k)

3. Subarrays with K Different Integers

   • Count subarrays with exactly k distinct integers
   • Time: O(n), Space: O(k)

Tips for Dynamic Size Sliding Window Problems

1. Identify the window expansion/contraction conditions
2. Maintain necessary state variables for window validation
3. Consider edge cases: empty input, single element
4. Optimize space usage by reusing variables
5. Use appropriate data structures for state tracking
6. Handle window size updates efficiently
7. Consider using helper functions for complex conditions
8. Validate window boundaries during adjustments

Happy Coding! 🚀