Sliding Window — Longest vs. Shortest Window ​

Common Interview Questions ​

1. Longest Substring Without Repeating Characters (LC 3)

   • Problem: Find the length of the longest substring with no repeating characters.
   • Sliding Window Signal: The keywords "longest substring" immediately point to a variable-size window.
   • Window State: A set is ideal here to enforce the "no repeating characters" rule with O(1) lookups.
   • Goal: This is the quintessential longest window problem. You expand the window, and if the new character is already in the set, you shrink from the left until it's removed. The max_len is updated after every valid expansion.

2. Minimum Size Subarray Sum (LC 209)

   • Problem: Find the minimum length of a contiguous subarray whose sum is at least a target value.
   • Sliding Window Signal: The keywords "minimum length" and "contiguous subarray" clearly indicate a variable-size window.
   • Window State: A single integer, current_sum, is all that's needed.
   • Goal: This is the canonical shortest window problem. You expand until current_sum >= target, update your min_len, and then shrink from the left as much as possible while the condition remains true, updating min_len each time.

3. Minimum Window Substring (LC 76)

   • Problem: Given strings s and t, find the minimum window in s which will contain all the characters in t (including duplicates).
   • Sliding Window Signal: "Minimum window" is a direct signal for a variable-size window aimed at finding a shortest match.
   • Window State: This is more complex. You need a hash map for the target character counts from t. You also need a counter (e.g., have_needed_chars) to track how many of the required characters you've satisfied in your current window.
   • Goal: A shortest window problem. Expand until the window is valid (have_needed_chars == total_needed_chars). Once valid, update the answer and immediately try to shrink from the left to find a tighter bound.

For variable-size windows, the goal is almost always to find either the longest or shortest subarray/substring that satisfies a condition. This choice dictates where you update your answer variable within the loop.

Longest Window ​

When looking for the longest window, you have a valid "candidate" window at every step after you expand. If the window is valid, it's a potential answer. You only shrink the window when it becomes invalid to restore the condition.

Logic: Expand the window. If it's valid, update the answer. If it's invalid, shrink until it's valid again.

Template: The answer update happens inside the main loop, right before you check the shrink condition (or right after, it doesn't matter as long as it's before the next expansion).

def find_longest_valid_window(arr, condition):
    left = 0
    max_len = 0
    # ... window state ...

    for right in range(len(arr)):
        # Expand window with arr[right]
        # ... update state ...

        # Shrink window ONLY IF condition is broken
        while not is_condition_met(...):
            # ... remove arr[left] from state ...
            left += 1
        
        # At this point, the window [left, right] is guaranteed to be valid.
        # This is the perfect time to update the longest length seen so far.
        max_len = max(max_len, right - left + 1)
        
    return max_len

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

Find the length of the longest substring without repeating characters.

def length_of_longest_substring(s: str) -> int:
    left = 0
    max_len = 0
    char_set = set() # Use a set to track unique characters in the window
    
    for right in range(len(s)):
        # Shrink window if the new character is already in our set
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
            
        # Expand window by adding the new character
        char_set.add(s[right])
        
        # Update max_len with the size of the current valid window
        max_len = max(max_len, right - left + 1)
        
    return max_len

Shortest Window ​

When looking for the shortest window, you can't consider a window a "candidate" until it first becomes valid. Once it's valid, you have a potential answer. Then, you try to make it even shorter by shrinking it from the left as much as possible while maintaining the condition.

Logic: Expand the window until the condition is met. Once met, record the length and then try to shrink from the left to find a potentially even shorter valid window.

Template: The answer update happens inside the while loop that governs the valid condition.

def find_shortest_valid_window(arr, condition_params):
    left = 0
    min_len = float('inf')
    # ... window state ...

    for right in range(len(arr)):
        # Expand window with arr[right]
        # ... update state ...

        # Shrink window AS MUCH AS POSSIBLE while the condition is still met
        while is_condition_met(...):
            # 1. Update the answer, because this is a valid candidate
            min_len = min(min_len, right - left + 1)
            
            # 2. Now, try to make it shorter
            # ... remove arr[left] from state ...
            left += 1
            
    return min_len if min_len != float('inf') else 0

Example Problem: Minimum Size Subarray Sum (LC 209) ​

Find the length of the shortest contiguous subarray whose sum is at least target.

def min_subarray_len(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]
        
        # Once the sum is valid, we have a candidate subarray.
        # Now, try to shrink it from the left.
        while current_sum >= target:
            # Update the minimum length
            min_len = min(min_len, right - left + 1)
            
            # Shrink the window
            current_sum -= nums[left]
            left += 1
            
    return min_len if min_len != float('inf') else 0

How the Algorithms Work ​

• Longest Window: The algorithm expands the window with the right pointer. At each step, it checks if the window is valid. If it becomes invalid, it shrinks from the left just enough to restore validity. The key is that the answer (max_len) is updated at every step where the window is valid, maximizing the recorded length over the entire pass.
• Shortest Window: The algorithm expands the window until a condition is met (e.g., sum >= target). As soon as the condition is met, it has found a potential answer and updates min_len. It then immediately tries to shrink the window from the left as much as possible, updating min_len at each step, to find the tightest possible window before continuing to expand with right.

Tricky Parts & Decision Points ​

1. Placement of max_len Update: For "longest" problems, the max_len = max(max_len, right - left + 1) line must be placed outside the shrinking while loop. This ensures you are measuring the size of every valid window.
2. Placement of min_len Update: For "shortest" problems, the min_len = min(min_len, right - left + 1) line must be placed inside the shrinking while loop. You only have a candidate answer when the condition is met, and you want to test its length immediately before making it shorter.
3. Initialization: When finding a minimum, you must initialize your answer to a very large number (float('inf')). When finding a maximum, you initialize to 0 or float('-inf'). Forgetting this can lead to incorrect results, especially if no valid window is found.