LeetCode (4): Sliding Window Technique

The sliding window technique is one of the most powerful and frequently used patterns in array and string problems. It allows us to efficiently solve problems that require examining contiguous subarrays or substrings without recalculating everything from scratch. If you've ever found yourself writing nested loops to check every possible subarray, sliding window is likely the optimization you need.

Understanding the Sliding Window Technique

At its core, the sliding window technique maintains a "window" of elements that slides through the array or string. Instead of checking all possible subarrays independently, we intelligently expand and contract the window based on certain conditions, reusing computations from previous windows.

Why Use Sliding Window?

Consider a problem where you need to find the maximum sum of any subarray of size k. A naive approach would iterate through all possible subarrays:

def naive_max_sum(arr, k):
    max_sum = float('-inf')
    for i in range(len(arr) - k + 1):
        current_sum = sum(arr[i:i+k])
        max_sum = max(max_sum, current_sum)
    return max_sum

This has time complexitybecause for each starting position, we sum k elements. With sliding window, we can achieve:

def sliding_window_max_sum(arr, k):
    if len(arr) < k:
        return 0
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i-k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

The key insight: when we slide the window one position to the right, we don't need to recalculate the entire sum. We subtract the element leaving the window and add the new element entering it.

Two Types of Sliding Windows

Sliding window problems fall into two main categories:

Fixed-Size Window

The window size remains constant throughout the algorithm. These problems are typically easier because we know exactly when to move the window.

Characteristics:

• Window size is predetermined (e.g., find maximum sum of subarray of size k)
• Window moves one position at a time
• Usually involves maintaining a running sum or count

Template:

def fixed_window_template(arr, k):
    if len(arr) < k:
        return []  # or handle edge case
    
    # Initialize first window
    window = arr[:k]
    result = process_window(window)  # or collect first result
    
    # Slide window
    for i in range(k, len(arr)):
        # Remove leftmost element
        window.pop(0)  # or use deque for O(1)
        # Add new element
        window.append(arr[i])
        # Process current window
        result = update_result(window, result)
    
    return result

Variable-Size Window

The window size changes dynamically based on conditions. These problems are more complex and often require two pointers (left and right) to track window boundaries.

Characteristics:

• Window size varies based on problem constraints
• Window expands when condition is not met
• Window contracts when condition is satisfied
• Often involves finding minimum/maximum window size

Template:

def variable_window_template(s):
    left = 0
    right = 0
    window = {}  # or Counter, or set
    
    while right < len(s):
        # Expand window
        add_to_window(s[right], window)
        right += 1
        
        # Contract window when condition is met
        while condition_satisfied(window):
            # Update result if needed
            update_result(left, right)
            
            # Remove leftmost element
            remove_from_window(s[left], window)
            left += 1
    
    return result

LeetCode 3: Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Analysis: This is a variable-size window problem. We need to maintain a window where all characters are unique. When we encounter a duplicate, we contract the window from the left until the duplicate is removed.

Solution:

def lengthOfLongestSubstring(s):
    if not s:
        return 0
    
    char_map = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # If character is already in window, move left pointer
        if s[right] in char_map and char_map[s[right]] >= left:
            left = char_map[s[right]] + 1
        
        char_map[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Java Version:

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    
    Map<Character, Integer> charMap = new HashMap<>();
    int left = 0;
    int maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (charMap.containsKey(c) && charMap.get(c) >= left) {
            left = charMap.get(c) + 1;
        }
        charMap.put(c, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Complexity Analysis:

• Time:
• Each character is visited at most twice (once by right, once by left)
• Space:
• Where m is the size of the character set (e.g., 26 for lowercase letters)

LeetCode 76: Minimum Window Substring

Problem: Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string.

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Analysis: This is a variable-size window problem where we need to find the smallest window containing all characters from t. We expand the window until all required characters are present, then contract to find the minimum valid window.

Solution:

def minWindow(s, t):
    if not s or not t or len(s) < len(t):
        return ""
    
    # Count characters in t
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    
    # Track current window
    window = {}
    left = 0
    right = 0
    valid = 0  # Number of distinct characters that satisfy requirement
    start = 0
    min_len = float('inf')
    
    while right < len(s):
        # Expand window
        c = s[right]
        right += 1
        
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
        
        # Contract window when all characters are found
        while valid == len(need):
            # Update minimum window
            if right - left < min_len:
                start = left
                min_len = right - left
            
            # Remove leftmost character
            d = s[left]
            left += 1
            
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    
    return "" if min_len == float('inf') else s[start:start + min_len]

Java Version:

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) {
        return "";
    }
    
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, minLen = Integer.MAX_VALUE;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        
        while (valid == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            
            char d = s.charAt(left);
            left++;
            
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

Complexity Analysis:

• Time:
• Each character in s is visited at most twice
• Space:
• For the hash maps

LeetCode 209: Minimum Size Subarray Sum

Problem: Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0.

Example:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Analysis: This is a variable-size window problem. We expand the window until the sum meets or exceeds the target, then contract to find the minimum valid window.

Solution:

def minSubArrayLen(target, nums):
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        # Contract window while sum is sufficient
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return 0 if min_length == float('inf') else min_length

Java Version:

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

Complexity Analysis:

• Time:
• Each element is visited at most twice
• Space:
• Only using a few variables

LeetCode 567: Permutation in String

Problem: Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

Example:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Analysis: This is a fixed-size window problem. We need to check if any window of size len(s1) in s2 contains the same character frequencies as s1.

Solution:

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    
    # Count characters in s1
    s1_count = {}
    for char in s1:
        s1_count[char] = s1_count.get(char, 0) + 1
    
    # Initialize window
    window_count = {}
    for i in range(len(s1)):
        char = s2[i]
        window_count[char] = window_count.get(char, 0) + 1
    
    # Check first window
    if window_count == s1_count:
        return True
    
    # Slide window
    for i in range(len(s1), len(s2)):
        # Add new character
        new_char = s2[i]
        window_count[new_char] = window_count.get(new_char, 0) + 1
        
        # Remove old character
        old_char = s2[i - len(s1)]
        window_count[old_char] -= 1
        if window_count[old_char] == 0:
            del window_count[old_char]
        
        # Check if window matches
        if window_count == s1_count:
            return True
    
    return False

Optimized Version (using array instead of dict):

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    
    s1_count = [0] * 26
    window_count = [0] * 26
    
    # Count s1 and first window of s2
    for i in range(len(s1)):
        s1_count[ord(s1[i]) - ord('a')] += 1
        window_count[ord(s2[i]) - ord('a')] += 1
    
    matches = sum(1 for i in range(26) if s1_count[i] == window_count[i])
    
    for i in range(len(s1), len(s2)):
        if matches == 26:
            return True
        
        # Add new character
        r = ord(s2[i]) - ord('a')
        window_count[r] += 1
        if window_count[r] == s1_count[r]:
            matches += 1
        elif window_count[r] == s1_count[r] + 1:
            matches -= 1
        
        # Remove old character
        l = ord(s2[i - len(s1)]) - ord('a')
        window_count[l] -= 1
        if window_count[l] == s1_count[l]:
            matches += 1
        elif window_count[l] == s1_count[l] - 1:
            matches -= 1
    
    return matches == 26

Complexity Analysis:

• Time:
• We slide through s2 once
• Space:
• Using fixed-size arrays (26 for lowercase letters)

LeetCode 438: Find All Anagrams in a String

Problem: Given two strings s and p, return an array of all the start indices of p's anagrams in s.

Example:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Analysis: This is similar to the permutation problem but we need to find all occurrences. We use a fixed-size window and check each position.

Solution:

def findAnagrams(s, p):
    if len(p) > len(s):
        return []
    
    result = []
    p_count = [0] * 26
    window_count = [0] * 26
    
    # Count p and first window
    for i in range(len(p)):
        p_count[ord(p[i]) - ord('a')] += 1
        window_count[ord(s[i]) - ord('a')] += 1
    
    matches = sum(1 for i in range(26) if p_count[i] == window_count[i])
    
    # Check first window
    if matches == 26:
        result.append(0)
    
    # Slide window
    for i in range(len(p), len(s)):
        # Add new character
        r = ord(s[i]) - ord('a')
        window_count[r] += 1
        if window_count[r] == p_count[r]:
            matches += 1
        elif window_count[r] == p_count[r] + 1:
            matches -= 1
        
        # Remove old character
        l = ord(s[i - len(p)]) - ord('a')
        window_count[l] -= 1
        if window_count[l] == p_count[l]:
            matches += 1
        elif window_count[l] == p_count[l] - 1:
            matches -= 1
        
        # Check if current window is anagram
        if matches == 26:
            result.append(i - len(p) + 1)
    
    return result

Java Version:

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) {
        return result;
    }
    
    int[] pCount = new int[26];
    int[] windowCount = new int[26];
    
    for (int i = 0; i < p.length(); i++) {
        pCount[p.charAt(i) - 'a']++;
        windowCount[s.charAt(i) - 'a']++;
    }
    
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (pCount[i] == windowCount[i]) {
            matches++;
        }
    }
    
    if (matches == 26) {
        result.add(0);
    }
    
    for (int i = p.length(); i < s.length(); i++) {
        int r = s.charAt(i) - 'a';
        windowCount[r]++;
        if (windowCount[r] == pCount[r]) {
            matches++;
        } else if (windowCount[r] == pCount[r] + 1) {
            matches--;
        }
        
        int l = s.charAt(i - p.length()) - 'a';
        windowCount[l]--;
        if (windowCount[l] == pCount[l]) {
            matches++;
        } else if (windowCount[l] == pCount[l] - 1) {
            matches--;
        }
        
        if (matches == 26) {
            result.add(i - p.length() + 1);
        }
    }
    
    return result;
}

Complexity Analysis:

• Time:
• Linear time complexity
• Space:
• Fixed-size arrays

Advanced Problem: Longest Substring with At Most K Distinct Characters

Problem: Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Solution:

def lengthOfLongestSubstringKDistinct(s, k):
    if not s or k == 0:
        return 0
    
    char_count = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # Add character to window
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # Contract window if distinct characters exceed k
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Complexity Analysis:

• Time:
• Each character visited at most twice
• Space:
• Hash map stores at most k+1 distinct characters

Complexity Analysis Patterns

Understanding time and space complexity for sliding window problems:

Time Complexity

Fixed-size window:

• Typicallywhere n is the array/string length
• Each element enters and leaves the window exactly once

Variable-size window:

• Typically
• Each element visited at most twice (once by right pointer, once by left pointer)
• This is because the left pointer never moves backward

Whyand not? Even though we have nested loops, the inner while loop doesn't reset left to 0. The left pointer only moves forward, so the total number of iterations is bounded by.

Space Complexity

Using hash maps/dictionaries:

-where k is the number of distinct characters/elements in the window - For lowercase letters: - For general characters:where m is character set size

Using arrays:

-if using fixed-size arrays (e.g., 26 for lowercase letters) -if array size depends on input range

Common Pitfalls and Debugging Tips

Pitfall 1: Off-by-One Errors

Problem: Incorrect window boundaries when calculating length.

Wrong:

max_length = max(max_length, right - left)  # Missing +1

Correct:

max_length = max(max_length, right - left + 1)

Tip: Remember that right - left + 1 gives the length of substring from left to right (inclusive).

Pitfall 2: Not Handling Empty Inputs

Problem: Forgetting to check for empty strings or arrays.

Solution: Always add edge case checks:

if not s or len(s) == 0:
    return 0  # or appropriate default

Pitfall 3: Incorrect Window Contraction Condition

Problem: Contracting window at wrong time or not contracting enough.

Example - Wrong:

while condition:
    # Only moves left once, might not be enough
    left += 1

Example - Correct:

while condition:
    # Properly remove element and update state
    remove_from_window(s[left])
    left += 1

Pitfall 4: Using List Instead of Deque for Fixed Window

Problem: Using list.pop(0) which isinstead of.

Wrong:

window = []
window.pop(0)  # O(n) operation

Correct:

from collections import deque
window = deque()
window.popleft()  # O(1) operation

Pitfall 5: Not Updating Result at Correct Time

Problem: Updating result before window is valid or after it becomes invalid.

Tip: Think carefully about when the window satisfies the condition:

• For "at least" conditions: Update result when condition is first met, then contract
• For "at most" conditions: Update result continuously as window expands

Debugging Tips

1. Print window state: Add print statements to track left, right, and window contents

   print(f"left={left}, right={right}, window={s[left:right+1]}")

2. Track character counts: For problems involving character frequencies, print the count map

   print(f"char_count: {char_count}")

3. Use small test cases: Start with simple examples to verify logic

   assert lengthOfLongestSubstring("abc") == 3
   assert lengthOfLongestSubstring("aaa") == 1

4. Check boundary conditions: Test with empty strings, single characters, and edge cases

5. Verify window invariants: Ensure your window always maintains the required properties

When to Use Sliding Window

Sliding window is appropriate when:

1. Contiguous subarrays/substrings: Problem asks about contiguous sequences
2. Optimization problems: Finding min/max length, sum, or count
3. Frequency/count problems: Involving character or element frequencies
4. Avoiding recomputation: When naive approach recalculates overlapping regions

Signs that sliding window might help:

• Problem mentions "subarray" or "substring"
• Need to find "minimum" or "maximum" window
• Involves "at most k" or "at least k" constraints
• Naive solution has nested loops checking all subarrays

Template Summary

Fixed-Size Window Template

def fixed_window(arr, k):
    if len(arr) < k:
        return []
    
    # Initialize first window
    window_sum = sum(arr[:k])  # or initialize window state
    result = window_sum  # or process first window
    
    # Slide window
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i-k] + arr[i]
        result = max(result, window_sum)  # or update result
    
    return result

Variable-Size Window Template

def variable_window(s):
    left = 0
    window = {}  # or Counter, set, etc.
    result = 0  # or []
    
    for right in range(len(s)):
        # Expand window
        add_to_window(s[right], window)
        
        # Contract window while condition violated
        while not is_valid(window):
            remove_from_window(s[left], window)
            left += 1
        
        # Update result
        result = update_result(left, right, result)
    
    return result

Q&A Section

Q1: How do I know if a problem is a sliding window problem?

A: Look for these indicators:

• Problem asks about contiguous subarrays or substrings
• Need to find minimum/maximum length or sum
• Involves constraints like "at most k distinct characters" or "sum >= target"
• Naive solution would check all possible subarrays (suggesting optimization needed)

Q2: What's the difference between fixed and variable window?

A:

• Fixed window: Size is predetermined (e.g., "find max sum of subarray of size k")
• Variable window: Size changes based on conditions (e.g., "find minimum window containing all characters")

Fixed windows are simpler - you know exactly when to move. Variable windows require tracking when conditions are met.

Q3: Why is sliding window O(n) and not O(n ²)?

A: Even with nested loops, the left pointer never moves backward. Each element is visited at most twice (once by right pointer expanding, once by left pointer contracting). Total iterations:.

Q4: Should I use a hash map or array for character counting?

A:

• Array: When character set is small and known (e.g., lowercase letters: 26, digits: 10)
• Hash map: When character set is large or unknown (e.g., Unicode characters)

Arrays are more efficient for small, fixed character sets.

Q5: How do I handle duplicate characters in the window?

A: Use a count map (dictionary or array) instead of a set. Track frequency of each character:

char_count = {}
char_count[char] = char_count.get(char, 0) + 1

When removing, decrement count and delete key when count reaches 0.

Q6: What if the window condition is complex (multiple constraints)?

A: Break it down: 1. Identify all constraints 2. Track state for each constraint 3. Expand window until all constraints might be satisfied 4. Contract until at least one constraint is violated 5. Update result when all constraints are satisfied

Q7: Can sliding window work with negative numbers?

A: Yes, but be careful:

• For "sum >= target" problems, contracting might not always reduce sum
• May need to track minimum sum ending at each position instead
• Consider using prefix sums or Kadane's algorithm for some cases

Q8: How do I find all valid windows, not just one?

A: Instead of returning early, collect all valid windows:

result = []
while condition:
    if window_valid:
        result.append(s[left:right+1])  # or append indices
    # Continue sliding

Q9: What's the best way to compare two frequency maps?

A: For small character sets, use arrays and compare directly:

if s1_count == window_count:  # Works for lists

For hash maps, compare key-value pairs:

if all(window.get(k, 0) == v for k, v in need.items()):

Or use a matches counter to track how many characters match.

Q10: How do I optimize space complexity?

A:

• Use arrays instead of hash maps when possible (fixed character set)
• Use a single variable to track "matches" instead of comparing entire maps
• Reuse variables instead of creating new data structures
• For some problems, you only need to track differences, not absolute counts

Related LeetCode Problems

Here are more problems to practice sliding window:

Easy:

• Maximum Average Subarray I
• Contains Duplicate II
• Best Time to Buy and Sell Stock

Medium:

• Longest Repeating Character Replacement
• Subarray Product Less Than K
• Maximum Points You Can Obtain from Cards
• Fruit Into Baskets
• Grumpy Bookstore Owner
• Max Consecutive Ones III

Hard:

• Sliding Window Maximum
• Minimum Window Subsequence
• Substring with Concatenation of All Words

Practice Recommendations

1. Start with fixed-size windows: Master the simpler pattern first
2. Practice variable windows: Work through problems requiring dynamic sizing
3. Focus on one language: Get comfortable with templates in Python or Java
4. Draw it out: Visualize the window sliding on paper for complex problems
5. Time yourself: Practice solving problems within 20-30 minutes
6. Review edge cases: Always test with empty inputs, single elements, and boundary conditions

Summary

The sliding window technique is a powerful optimization for problems involving contiguous subarrays or substrings. Key takeaways:

1. Two types: Fixed-size (predetermined) and variable-size (dynamic based on conditions)
2. Time complexity: Typicallybecause each element is visited at most twice
3. Space complexity:where k is the number of distinct elements, oftenfor fixed character sets
4. Common patterns: Use hash maps or arrays to track window state, expand until condition met, contract to optimize
5. Templates: Memorize the basic templates and adapt them to specific problems

Mastering sliding window will help you solve many array and string problems efficiently. Key: recognizing when to use it and correctly implementing the expand/contract logic. Practice with the problems listed above, and soon you'll be able to identify and solve sliding window problems quickly.

Remember: if you find yourself checking all possible subarrays with nested loops, sliding window is likely the optimization you need. The technique transformsorsolutions intosolutions, making it essential for efficient algorithm design.