Sliding Window — Arrays vs. Strings ​

Common Interview Questions ​

1. Minimum Size Subarray Sum (LC 209)

   • Problem: Find the minimum length of a contiguous subarray in an array of integers whose sum is at least a target.
   • Sliding Window Signal: "Minimum length" and "contiguous subarray" on an array.
   • Window State: This is a classic array problem. The state is a single integer, current_sum. Be aware that the simple shrinking logic works here because the problem specifies positive integers, ensuring the sum condition is monotonic.
   • Goal: A "shortest window" problem.

2. Longest Substring with At Most K Distinct Characters (LC 340)

   • Problem: Find the length of the longest substring in a string that contains at most K distinct characters.
   • Sliding Window Signal: "Longest substring" on a string.
   • Window State: This is a classic string problem. The state is a hash map tracking the frequency of characters.
   • Goal: A "longest window" problem.

3. Find All Anagrams in a String (LC 438)

   • Problem: Find all starting indices of anagrams of a pattern string p within a larger string s.
   • Sliding Window Signal: Fixed-size window on a string.
   • Window State: A string problem where the state is best handled by frequency maps (either a Counter or a fixed-size array if the character set is limited).
   • Goal: Compare the frequency map of the window to the target map at each step.

The sliding window technique applies identically to both arrays and strings. Both are ordered, indexable collections. However, the way you store the "state" of the window often differs based on the type of data and the problem constraints.

Arrays ​

When working with arrays of numbers, the window's state is often an aggregate value or a frequency map.

• State:

  • current_sum for sum-related problems.
  • defaultdict(int) or dict for frequency counts of numbers.
  • Can be other structures like a deque for finding min/max in a window.

• Pitfalls:

  • Integer Overflow: If summing up numbers, be mindful of potential overflow, though this is less of a concern in Python where integers have arbitrary precision.
  • Negative Numbers: Problems involving sums can become much trickier with negative numbers. The monotonic property of a sum (i.e., adding a positive number increases the sum) may no longer hold, which can break the standard while current_sum > target shrinking logic.

Example Problem: Minimum Size Subarray Sum (LC 209) - Array of Numbers ​

This is a classic array-based window problem where the state is a simple sum.

def min_subarray_len_array(target: int, nums: list[int]) -> int:
    left = 0
    min_len = float('inf')
    current_sum = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
            
    return min_len if min_len != float('inf') else 0

Strings ​

When working with strings, the window's state is almost always a frequency map of its characters.

• State:

  • defaultdict(int) is excellent for tracking character counts.
  • A fixed-size array (e.g., [0] * 26 for lowercase English letters) can be a highly efficient alternative if the character set is small and known.
  • A set is perfect for tracking unique characters when counts don't matter.

• Optimization:

  • Using ord(char) - ord('a') is the standard, fast way to map lowercase English letters to array indices 0-25. This is a common and expected optimization in interviews.

Example Problem: Longest Substring Without Repeating Characters (LC 3) - String ​

This is a classic string-based window problem where the state is the set of unique characters.

def length_of_longest_substring_string(s: str) -> int:
    left = 0
    max_len = 0
    char_set = set() # State is a set of unique characters
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
            
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
        
    return max_len

Example Problem: Find All Anagrams in a String (LC 438) - String with Array State ​

Given two strings s and p, return an array of all the start indices of p's anagrams in s. This is a fixed-size window problem where the window state is a character frequency map.

from collections import Counter

def find_all_anagrams(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []

    p_counts = Counter(p)
    s_counts = Counter()
    
    result = []
    left = 0
    
    for right in range(len(s)):
        s_counts[s[right]] += 1
        
        # Shrink window if it's too large
        if (right - left + 1) > len(p):
            s_counts[s[left]] -= 1
            if s_counts[s[left]] == 0:
                del s_counts[s[left]]
            left += 1
            
        # Compare window to target
        if s_counts == p_counts:
            result.append(left)
            
    return result

How the Algorithm Works ​

The underlying sliding window mechanism is identical for both arrays and strings. A right pointer expands the window and a left pointer contracts it based on a condition. The primary difference is the data structure used to maintain the window's state: arrays of numbers typically use sums or integer frequency maps, while strings almost always use character frequency maps (e.g., a hash map or a fixed-size array).

Tricky Parts & Decision Points ​

1. Choosing the State Tracker: For strings with a limited character set (like lowercase English letters), using a fixed-size array of 26 integers is faster than a hash map and shows you're thinking about performance. For arrays of arbitrary numbers, a hash map (defaultdict) is the only feasible choice for tracking frequencies.
2. Handling Negative Numbers: This is a key challenge for array-based problems. If an array can contain negative numbers, a sum-based condition may no longer be monotonic (e.g., adding a negative number decreases the sum). This can break simple shrinking logic (while current_sum > target), forcing you to consider more complex approaches like prefix sums with a hash map.
3. Hashable State: When comparing the state of a window (like in the anagram problem), the state must be hashable. A Counter object in Python is hashable, but a standard dict is not. Freezing a Counter or converting its items to a frozenset can work, but comparing two Counter objects directly (s_counts == p_counts) is the cleanest solution.