Sliding Window

The sliding window technique is used when you need to find a contiguous subarray or substring that satisfies certain conditions. It maintains a window of elements and efficiently moves it across the data structure.

When to Use

Problems involving contiguous subarrays or substrings
Finding maximum/minimum sum, length, or count in a window
Questions asking for 'longest substring' or 'shortest subarray'
Problems where you need to track elements within a range

Common Patterns

Fixed Window

Window size is constant throughout the problem

Example: Maximum sum of k consecutive elements

Variable Window

Window size changes based on conditions

Example: Longest substring without repeating characters

Code Templates

Python

# Variable Window Template
def sliding_window(s):
    left = 0
    window = {}  # or set, or counter
    result = 0
    
    for right in range(len(s)):
        # Expand window: add s[right]
        window[s[right]] = window.get(s[right], 0) + 1
        
        # Shrink window while condition violated
        while condition_violated(window):
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        
        # Update result
        result = max(result, right - left + 1)
    
    return result

C++

// Variable Window Template
int slidingWindow(string s) {
    int left = 0;
    unordered_map<char, int> window;
    int result = 0;
    
    for (int right = 0; right < s.length(); right++) {
        // Expand window: add s[right]
        window[s[right]]++;
        
        // Shrink window while condition violated
        while (conditionViolated(window)) {
            window[s[left]]--;
            if (window[s[left]] == 0) {
                window.erase(s[left]);
            }
            left++;
        }
        
        // Update result
        result = max(result, right - left + 1);
    }
    
    return result;
}