Loading learning content...
Fixed-size sliding windows are powerful, but they're limited to problems where the answer involves a predetermined window size. What if instead you need to find:
These problems share a common structure: the window size isn't given—it's what you're trying to discover. You need a window that expands to explore and shrinks to refine.
Welcome to variable-size sliding windows, where the algorithmic challenge shifts from "what state to track" to "when to shrink the window."
By the end of this page, you will master the expand-shrink pattern for variable windows, understand when to expand vs shrink, implement multiple classic variable-window problems, and recognize the crucial difference between 'longest valid' and 'shortest valid' problem structures.
Variable-size sliding windows operate on a fundamental rhythm: expand to explore possibilities, shrink to maintain validity. Think of it as an accordion that stretches and contracts as it slides across the array.
The Core Logic:
Expand (right pointer moves right): Add new elements to explore larger windows. This is the "optimistic" phase—you're trying to find better solutions by including more.
Shrink (left pointer moves right): Remove elements from the start to restore a property or optimize further. This is the "corrective" phase—you're eliminating elements that violate constraints or are no longer needed.
The art of variable-size windows lies in knowing when to switch from expanding to shrinking.
1234567891011121314151617181920212223242526272829303132333435363738
def variable_sliding_window(arr, constraint): """ Variable-size sliding window template. Time Complexity: O(n) - each element touched at most twice (once by right pointer, once by left pointer) Space Complexity: O(1) or O(k) depending on state requirements """ n = len(arr) left = 0 result = initial_result_value # State tracking (window contents, counts, etc.) window_state = initialize_state() # Right pointer iterates through the entire array for right in range(n): # ======================================== # STEP 1: EXPAND - Add arr[right] to window # ======================================== update_state_on_entry(window_state, arr[right]) # ======================================== # STEP 2: SHRINK - While window is invalid # ======================================== while window_is_invalid(window_state, constraint): # Remove arr[left] from window update_state_on_exit(window_state, arr[left]) left += 1 # ======================================== # STEP 3: RECORD - Window is now valid # ======================================== # Update result based on current valid window # Window spans [left, right], size = right - left + 1 result = update_result(result, window_state, left, right) return resultAfter the shrink loop exits, the window [left, right] is guaranteed to be valid (or empty). This is your invariant. Every valid window is considered, and you record results only for valid windows. This ensures correctness.
The shrinking decision distinguishes variable-size windows from fixed-size ones. Let's analyze the two primary problem patterns:
Critical Difference:
In "longest valid" problems, you shrink reactively—only when you must. You're trying to keep the window as large as possible.
In "shortest valid" problems, you shrink proactively—whenever you have a valid window. You're trying to minimize.
This difference changes where you record your result:
12345678910111213141516171819202122232425262728293031323334353637
# PATTERN 1: Longest Valid Windowdef longest_valid_window(arr, constraint): """Shrink when invalid, record after shrinking.""" left = 0 max_length = 0 for right in range(len(arr)): add_to_window(right) while window_is_invalid(): remove_from_window(left) left += 1 # Window is now valid (or empty) # Record the valid window's length max_length = max(max_length, right - left + 1) return max_length # PATTERN 2: Shortest Valid Windowdef shortest_valid_window(arr, constraint): """Shrink while valid, record before shrinking.""" left = 0 min_length = float('inf') for right in range(len(arr)): add_to_window(right) while window_is_valid(): # Record BEFORE shrinking (window is still valid) min_length = min(min_length, right - left + 1) remove_from_window(left) left += 1 # After shrinking, window might be invalid return min_length if min_length != float('inf') else 0The most common mistake is using the 'longest' pattern for a 'shortest' problem or vice versa. Before implementing, ask: 'Am I trying to maximize or minimize the window?' This determines your shrink condition and where you record results.
This is perhaps the most famous variable-size sliding window problem. Let's solve it step by step.
Problem Statement:
Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeating characters.
Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest; single character = no repeats.
Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest.
Constraint: All characters in the window must be unique (no repeats). Goal: Maximize window size → Use "longest valid" pattern.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
def length_of_longest_substring(s): """ Find length of longest substring without repeating characters. Time: O(n) - each character visited at most twice (by right, by left) Space: O(min(n, charset_size)) - hash set stores unique chars Strategy: - Maintain a set of characters in current window - Expand by adding new character - If character already in set, shrink until it's removed - Track maximum valid window size """ char_set = set() left = 0 max_length = 0 for right in range(len(s)): current_char = s[right] # Shrink while the current character would be a duplicate while current_char in char_set: char_set.remove(s[left]) left += 1 # Add current character (now guaranteed unique in window) char_set.add(current_char) # Update maximum (window is valid here) max_length = max(max_length, right - left + 1) return max_length # Trace: s = "abcabcbb"## right=0 (a): char_set = {a}, window = "a", max = 1# right=1 (b): char_set = {a, b}, window = "ab", max = 2# right=2 (c): char_set = {a, b, c}, window = "abc", max = 3# right=3 (a): 'a' in set!# Remove s[0]='a': char_set = {b, c}, left = 1# Now 'a' not in set, add it: char_set = {b, c, a}# window = "bca", max = 3# right=4 (b): 'b' in set!# Remove s[1]='b': char_set = {c, a}, left = 2# Now 'b' not in set, add it: char_set = {c, a, b}# window = "cab", max = 3# right=5 (c): 'c' in set!# Remove s[2]='c': char_set = {a, b}, left = 3# Now 'c' not in set, add it: char_set = {a, b, c}# window = "abc", max = 3# right=6 (b): 'b' in set!# Remove s[3]='a': char_set = {b, c}, left = 4# 'b' still in set!# Remove s[4]='b': char_set = {c}, left = 5# Now 'b' not in set, add it: char_set = {c, b}# window = "cb", max = 3# right=7 (b): 'b' in set!# Remove s[5]='c': char_set = {b}, left = 6# 'b' still in set!# Remove s[6]='b': char_set = {}, left = 7# Add 'b': char_set = {b}# window = "b", max = 3## Result: 3Instead of shrinking one character at a time, track the last index of each character. When you find a duplicate, jump left directly to one past the duplicate's last position. This avoids the inner while loop but adds bookkeeping. Both approaches are O(n); choose based on clarity vs constant factor.
123456789101112131415161718192021222324
def length_of_longest_substring_optimized(s): """ Optimized version using hash map for direct jumps. Instead of removing characters one by one, we jump left directly past the duplicate. """ char_index = {} # char -> most recent index left = 0 max_length = 0 for right, char in enumerate(s): # If char seen before AND its index is within current window if char in char_index and char_index[char] >= left: # Jump left to just after the previous occurrence left = char_index[char] + 1 # Update last seen index char_index[char] = right # Update maximum max_length = max(max_length, right - left + 1) return max_lengthThis is a generalization of the previous problem—instead of requiring all unique characters, we allow at most k distinct characters.
Problem Statement:
Given a string s and integer k, find the length of the longest substring that contains at most k distinct characters.
Example:
Input: s = "eceba", k = 2
Output: 3
Explanation: "ece" has 2 distinct characters (e, c).
Input: s = "aa", k = 1
Output: 2
Explanation: "aa" has 1 distinct character.
Constraint: Number of distinct characters ≤ k Goal: Maximize window size → "longest valid" pattern
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
from collections import defaultdict def longest_substring_k_distinct(s, k): """ Find longest substring with at most k distinct characters. Time: O(n) Space: O(k) - hash map stores at most k+1 entries Strategy: - Track frequency of each character in window - Track count of distinct characters - Shrink when distinct > k """ if k == 0: return 0 char_count = defaultdict(int) distinct = 0 left = 0 max_length = 0 for right, char in enumerate(s): # Add character to window if char_count[char] == 0: distinct += 1 # New distinct character char_count[char] += 1 # Shrink while too many distinct characters while distinct > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: distinct -= 1 # Lost a distinct character left += 1 # Window is valid (distinct <= k) max_length = max(max_length, right - left + 1) return max_length # Trace: s = "eceba", k = 2## right=0 (e): distinct=1, window="e", max=1# right=1 (c): distinct=2, window="ec", max=2# right=2 (e): distinct=2, window="ece", max=3# right=3 (b): distinct=3 > k=2!# Remove 'e': count[e]=1, distinct still 3# left=1# Remove 'c': count[c]=0, distinct=2# left=2# Now distinct=2, window="eb", max=3# right=4 (a): distinct=3 > k=2!# Remove 'e': count[e]=0, distinct=2# left=3# Now distinct=2, window="ba", max=3## Result: 3Tracking 'distinct count' by incrementing when frequency goes 0→1 and decrementing when 1→0 is a powerful pattern. It avoids scanning the hash map to count non-zero entries. Use this whenever you need to know how many unique elements are in the window.
Now let's see a "shortest valid" problem—where we shrink proactively to find the smallest valid window.
Problem Statement:
Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is ≥ target. Return 0 if no such subarray exists.
Example:
Input: nums = [2, 3, 1, 2, 4, 3], target = 7
Output: 2
Explanation: [4, 3] has sum 7, length 2.
Input: nums = [1, 4, 4], target = 4
Output: 1
Explanation: [4] has sum 4, length 1.
Input: nums = [1, 1, 1, 1, 1, 1, 1, 1], target = 11
Output: 0
Explanation: Sum of entire array is 8 < 11.
Constraint: sum ≥ target (valid when this holds) Goal: Minimize window size → "shortest valid" pattern
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
def min_subarray_len(target, nums): """ Find minimum length subarray with sum >= target. Time: O(n) - each element added once, removed at most once Space: O(1) Strategy: - Expand right, adding to window sum - When sum >= target (valid!), record and shrink - Continue shrinking while still valid to find minimum Note: This only works for POSITIVE integers. Negative numbers break the monotonic property. """ n = len(nums) left = 0 window_sum = 0 min_length = float('inf') for right in range(n): # Expand: add current element window_sum += nums[right] # Shrink WHILE valid (trying to minimize) while window_sum >= target: # Record BEFORE shrinking (window is still valid) min_length = min(min_length, right - left + 1) # Shrink by removing left element window_sum -= nums[left] left += 1 return min_length if min_length != float('inf') else 0 # Trace: nums = [2, 3, 1, 2, 4, 3], target = 7## right=0: sum=2, not valid# right=1: sum=5, not valid# right=2: sum=6, not valid# right=3: sum=8 >= 7, VALID!# min_length = 4 (window [2,3,1,2])# Shrink: sum=8-2=6, left=1# sum=6 < 7, stop shrinking# right=4: sum=6+4=10 >= 7, VALID!# min_length = min(4, 4) = 4 (window [3,1,2,4])# Shrink: sum=10-3=7, left=2# sum=7 >= 7, STILL VALID!# min_length = min(4, 3) = 3 (window [1,2,4])# Shrink: sum=7-1=6, left=3# sum=6 < 7, stop shrinking# right=5: sum=6+3=9 >= 7, VALID!# min_length = min(3, 3) = 3 (window [2,4,3])# Shrink: sum=9-2=7, left=4# sum=7 >= 7, STILL VALID!# min_length = min(3, 2) = 2 (window [4,3])# Shrink: sum=7-4=3, left=5# sum=3 < 7, stop shrinking## Result: 2This algorithm relies on monotonicity: adding elements can only increase the sum, removing can only decrease it. With negative numbers, removing an element might INCREASE the sum, breaking the shrinking logic. For arrays with negatives, you'd need prefix sums with binary search or other techniques.
Contrast with 'Longest Valid' Pattern:
Notice how the logic differs from "longest substring" problems:
| Aspect | Longest Valid | Shortest Valid |
|---|---|---|
| Shrink when | Window is invalid | Window is valid |
| Record when | After shrinking | Before shrinking |
| Shrink goal | Restore validity | Improve result |
| Result update | After shrink loop | Inside shrink loop |
This is one of the most challenging and celebrated sliding window problems. It combines multiple state-tracking elements and requires careful shrinking logic.
Problem Statement:
Given strings s and t, find the minimum window substring of s that contains all characters of t (including duplicates). If no such window exists, return "".
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" contains A, B, and C.
Input: s = "a", t = "a"
Output: "a"
Input: s = "a", t = "aa"
Output: ""
Explanation: 't' has two 'a's, but 's' has only one.
Constraint: Window contains all characters of t (with correct frequencies) Goal: Minimize window size → "shortest valid" pattern
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
from collections import defaultdict, Counter def min_window(s, t): """ Find minimum window in s containing all characters of t. Time: O(|s| + |t|) Space: O(|s| + |t|) for hash maps and result Strategy: 1. Build frequency map of t 2. Track how many t-characters we've "satisfied" in window 3. Expand until we satisfy all 4. Shrink while maintaining validity, tracking minimum """ if not s or not t or len(s) < len(t): return "" # Frequency of characters we need t_freq = Counter(t) required = len(t_freq) # Number of distinct chars we need # Tracking window state window_freq = defaultdict(int) formed = 0 # How many chars have met required frequency # Result tracking min_len = float('inf') result_start = 0 left = 0 for right, char in enumerate(s): # Expand: add character to window window_freq[char] += 1 # Check if this character's requirement is now satisfied if char in t_freq and window_freq[char] == t_freq[char]: formed += 1 # Shrink while window is valid (all chars satisfied) while formed == required: # Record if this is the smallest valid window window_size = right - left + 1 if window_size < min_len: min_len = window_size result_start = left # Try to shrink by removing left character left_char = s[left] window_freq[left_char] -= 1 # Check if removing broke a requirement if left_char in t_freq and window_freq[left_char] < t_freq[left_char]: formed -= 1 left += 1 if min_len == float('inf'): return "" return s[result_start:result_start + min_len] # Trace: s = "ADOBECODEBANC", t = "ABC"# t_freq = {A:1, B:1, C:1}, required = 3## Expand until formed = 3:# right=0 (A): window_freq[A]=1, formed=1# right=1 (D): no effect# right=2 (O): no effect# right=3 (B): window_freq[B]=1, formed=2# right=4 (E): no effect# right=5 (C): window_freq[C]=1, formed=3 (VALID!)## Shrink:# Window "ADOBEC" (length 6), record as candidate# Remove A: window_freq[A]=0 < t_freq[A]=1, formed=2# left=1, stop shrinking## Continue expanding until formed=3 again...# right=10 (A): formed becomes 3 again## Shrink:# Window "ECODEBA" (length 7) > 6, not better# etc.## Eventually find "BANC" (length 4) as minimumThe 'formed' variable is crucial: it tracks how many distinct characters have MET THEIR REQUIRED FREQUENCY. We only increment when window_freq equals t_freq (not when it exceeds). We only decrement when dropping below. This elegant counting avoids comparing entire maps on every iteration.
Variable-size sliding windows appear to have nested loops (the outer for loop and inner while loop), which might suggest O(n²) complexity. Let's prove it's actually O(n).
The Key Insight: Amortized Analysis
Consider what happens to the left pointer:
Similarly, the right pointer:
Total pointer movements: 2n (n for right + at most n for left)
Each element is processed at most twice:
Operations per element: O(1) (hash map operations, arithmetic)
Total time: O(2n) = O(n)
| Component | Operations | Notes |
|---|---|---|
| Right pointer movement | n | One step per outer loop iteration |
| Left pointer movement | ≤ n | Never moves left, total distance ≤ n |
| Add to window | n | Each element added once |
| Remove from window | ≤ n | Each element removed at most once |
| State update per operation | O(1) | Hash map, arithmetic |
| Total | O(n) | Linear in array length |
Imagine each element 'pays' for its own entry and exit. Some elements 'pay' more at certain steps (when the left pointer moves multiple times), but they're using up the 'credit' from previous elements that didn't shrink. The total cost balances out to 2n operations.
Space Complexity:
Space complexity varies by problem:
For most sliding window problems, space is O(1) or O(k) where k is small.
You've now mastered the more challenging variant of sliding windows. Let's consolidate:
What's Next:
You now have the templates and intuition for both fixed and variable sliding windows. The final page brings it all together with classic problems that test your pattern recognition and decision-making. You'll see problems where the sliding window approach isn't immediately obvious, and learn to recognize the technique in disguise.
You can now tackle problems asking for the longest substring, shortest subarray, or minimum window satisfying constraints. You understand when to shrink and where to record results. Next: putting it all together with classic problems and pattern recognition.