Complexity Analysis
Each element is visited at most twice—once when expanding right, once when contracting left. Space depends on what you track (character set, counts). For character problems, O(min(n, alphabet_size)).
Recognize This Pattern When...
Pattern Signals
- "Longest substring/subarray" with a constraint
- "Shortest substring/subarray" that satisfies a condition
- "At most k" distinct elements, flips, changes allowed
- Window size not given—determined by a condition
- "Minimum window" containing certain elements
Preconditions
- Working with contiguous subarrays or substrings
- Constraint has monotonic property: if invalid, expanding makes it worse (or stays invalid)
- Can efficiently check validity and update state as window changes
When NOT to Use
- Array has negative numbers and you're tracking sum (sum doesn't monotonically increase)
- Looking for non-contiguous elements (subsequences, not subarrays)
- Need all combinations, not just the optimal window
- Constraint doesn't have monotonic property
Why It Works
Once a window becomes invalid, adding more elements won't fix it—you must shrink from the left. By expanding right greedily and shrinking left only when necessary, you explore all valid windows without checking every possible subarray. Each element enters and exits the window at most once, giving O(n) time.
The Analogy
Imagine stretching a rubber band between two fingers. You keep stretching it to the right until it's about to snap (constraint violated). Then you release tension from the left until it's safe again. You're looking for the longest stretch that doesn't break.
The Canonical Problem
Longest Substring Without Repeating Characters
mediumGiven a string s, find the length of the longest substring without repeating characters.
Solve on LeetCodeAlgorithm Template
Generic template you can adapt to most sliding window (variable size) problems.
def variable_sliding_window(s):
left = 0
max_len = 0
# Track window state (set, map, counter, etc.)
seen = set()
for right in range(len(s)):
# Expand: add right element to window
# Shrink: while window is invalid
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
# Update result (window is valid here)
max_len = max(max_len, right - left + 1)
return max_lenImplementations
Complete examples with explanations. Copy-paste and adapt to your problem.
def length_of_longest_substring(s: str) -> int:
"""
Find the longest substring without repeating characters.
Time: O(n), Space: O(min(n, alphabet_size))
"""
left = 0
max_len = 0
seen = set()
for right in range(len(s)):
# Shrink window until no duplicate
while s[right] in seen:
seen.remove(s[left])
left += 1
# Add current character
seen.add(s[right])
# Update max (window is valid)
max_len = max(max_len, right - left + 1)
return max_len
# Example usage
print(length_of_longest_substring("abcabcbb")) # 3 ("abc")
print(length_of_longest_substring("bbbbb")) # 1 ("b")
# Variant: Minimum Window Substring
def min_window(s: str, t: str) -> str:
"""Find minimum window in s containing all characters of t."""
from collections import Counter
if not t or not s:
return ""
target = Counter(t)
required = len(target) # Unique chars needed
left = 0
formed = 0 # Unique chars in window with required count
window_counts = {}
result = (float("inf"), 0, 0) # (length, left, right)
for right in range(len(s)):
# Expand: add right character
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in target and window_counts[char] == target[char]:
formed += 1
# Shrink while valid to find minimum
while formed == required:
# Update result
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
# Remove left character
left_char = s[left]
window_counts[left_char] -= 1
if left_char in target and window_counts[left_char] < target[left_char]:
formed -= 1
left += 1
return "" if result[0] == float("inf") else s[result[1]:result[2] + 1]Python implementation showing the "longest" pattern (expand then shrink) and the "shortest/minimum" pattern (shrink while valid). Note how the shrinking logic differs: for longest, shrink while invalid; for shortest, shrink while valid.
/**
* Find the longest substring without repeating characters.
*
* Time: O(n), Space: O(min(n, alphabet_size))
*/
function lengthOfLongestSubstring(s) {
let left = 0;
let maxLen = 0;
const seen = new Set();
for (let right = 0; right < s.length; right++) {
// Shrink window until no duplicate
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
// Add current character
seen.add(s[right]);
// Update max (window is valid)
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Example usage
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("pwwkew")); // 3
// Variant: Longest Repeating Character Replacement
function characterReplacement(s, k) {
const counts = new Array(26).fill(0);
let left = 0;
let maxCount = 0; // Most frequent char in current window
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const idx = s.charCodeAt(right) - 65; // A=0, B=1, etc.
counts[idx]++;
maxCount = Math.max(maxCount, counts[idx]);
// Window is invalid if we need more than k replacements
// (window_size - most_frequent > k)
while (right - left + 1 - maxCount > k) {
counts[s.charCodeAt(left) - 65]--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Variant: Fruit Into Baskets (at most 2 types)
function totalFruit(fruits) {
const basket = new Map(); // fruit type -> count
let left = 0;
let maxFruits = 0;
for (let right = 0; right < fruits.length; right++) {
// Add fruit to basket
basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);
// Shrink while more than 2 types
while (basket.size > 2) {
const leftFruit = fruits[left];
basket.set(leftFruit, basket.get(leftFruit) - 1);
if (basket.get(leftFruit) === 0) {
basket.delete(leftFruit);
}
left++;
}
maxFruits = Math.max(maxFruits, right - left + 1);
}
return maxFruits;
}JavaScript implementation showing three common variants: unique characters, character replacement (with k budget), and limited types (fruit baskets). Each follows expand-then-shrink pattern with different validity conditions.
Pattern Variations
Longest with Constraint
O(n) / O(k)Find longest subarray/substring satisfying a condition. Expand right, shrink left while invalid, update max when valid.
Shortest/Minimum with Requirement
O(n) / O(k)Find shortest subarray satisfying a requirement. Expand until valid, then shrink while still valid to find minimum.
Count of Valid Subarrays
O(n) / O(k)Count all subarrays satisfying a constraint. Often uses "exactly k" = "at most k" - "at most k-1" trick.
At Most K Distinct
O(n) / O(k)Longest substring with at most k distinct characters. Classic variable window with hash map tracking.
Practice Problems
| Problem | Difficulty | Type | Notes |
|---|---|---|---|
| Longest Substring Without Repeating Characters | medium | canonical | The classic variable window problem. Asked at Meta, Amazon, Bloomberg constantly. |
| Minimum Size Subarray Sum | medium | variant | Minimum window variant. Shrink while valid, not while invalid. |
| Longest Repeating Character Replacement | medium | variant | Track most frequent char in window. Window invalid if replacements > k. |
| Fruit Into Baskets | medium | variant | At most 2 distinct types. Same as "longest substring with 2 distinct chars". |
| Max Consecutive Ones III | medium | variant | Can flip at most k zeros. Track zero count in window. |
| Minimum Window Substring | hard | follow-up | Hard classic. Minimum window containing all target chars. Meta/LinkedIn favorite. |
| Subarrays with K Different Integers | hard | follow-up | Count subarrays with exactly k distinct. Use atMost(k) - atMost(k-1) trick. |
| Longest Subarray of 1's After Deleting One Element | medium | variant | Allow at most one 0 in window. Special case: all 1s requires deletion. |
Interview Tips
- Clarify: "longest" means maximize, "shortest/minimum" means minimize—they have different shrink conditions
- For "longest": shrink while INVALID. For "shortest": shrink while VALID
- Always explain WHY the algorithm is O(n): each element enters and exits window once
- Ask about character set—26 letters means O(1) space with int[26] array
- For "exactly k" problems, mention the atMost(k) - atMost(k-1) transformation
Common Follow-up Questions
What if the array has negative numbers?
CommonFor sum-based problems like "minimum subarray with sum >= target", negative numbers break the monotonic property—expanding the window doesn't always increase the sum. You need a different approach: prefix sums with binary search (O(n log n)) or monotonic deque (O(n)).
How do you find exactly k distinct, not at most k?
CommonFor counting subarrays: use the identity count(exactly k) = count(atMost k) - count(atMost k-1). For finding the longest: this identity doesn't apply to lengths. Instead, track distinct count and only update max_len when count == k exactly. Alternatively, use two pointers with a minimum window approach.
Can you solve it without the inner while loop?
For some problems, yes. Instead of shrinking until valid, you can allow the window to be "overflowing" and just not update the max when invalid. The window size only grows or stays same. Works for Longest Repeating Character Replacement. Slightly trickier to reason about.
How would you return the actual substring instead of just the length?
CommonTrack start_index and max_length. When you update max, store: start_index = left, max_length = right - left + 1. At the end, return s[start_index:start_index + max_length].
What if we need all minimum windows, not just one?
First find the minimum length using standard algorithm. Then do a second pass: whenever you find a valid window of that minimum length, record it. Or modify the algorithm to store all windows when you update the minimum.
Common Mistakes
Using "if" instead of "while" to shrink the window
# WRONG: Only shrinks once per iteration
for right in range(len(s)):
seen.add(s[right])
if s[right] in seen: # Should be "while"
seen.remove(s[left])
left += 1Fix: Use "while" to shrink the window. The new element might require removing multiple elements from the left to make the window valid again. Single "if" only removes one element.
Updating result while window is invalid
# WRONG: Updating max before window is valid
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
max_len = max(max_len, right - left + 1) # BEFORE adding s[right]!
seen.add(s[right])Fix: Update the result AFTER the window is valid. For longest: add element, shrink if needed, THEN update max. The order matters—update max only when the window represents a valid state.
Initializing min_length to 0 for minimum window problems
# WRONG: Can never find a window shorter than 0
min_len = 0
for right in range(len(s)):
# ...
min_len = min(min_len, right - left + 1) # Always stays 0Fix: Initialize min_len to float("inf") or len(s) + 1 for minimum problems. You want the first valid window to become the new minimum. Check at the end if min_len is still infinity (no valid window found).
Forgetting to remove element from tracking when shrinking
# WRONG: Not removing from set when shrinking
while len(seen) > k:
left += 1 # Moved pointer but didn't update seen!Fix: When shrinking, always update your tracking data structure. Remove s[left] from the set/map BEFORE incrementing left. The order is: update state, then move pointer.
Frequently Asked Questions
How is variable sliding window different from two pointers?
Variable sliding window is a specific two-pointer pattern where both pointers move in the same direction (left to right), and the space between them represents a window with some property. Classic two pointers (like Two Sum II) often have pointers moving toward each other. Sliding window cares about the content BETWEEN pointers; classic two pointers often cares about values AT the pointers.
Why does each element get visited at most twice?
The right pointer visits each element exactly once (the for loop). The left pointer can only move right (never left), and it can never pass the right pointer. So left visits at most n elements total across all iterations. Combined: at most 2n operations, which is O(n).
When do I use a set vs a map for tracking?
Use a set when you only care about presence/absence (e.g., "no repeating characters"). Use a map (Counter) when you need counts (e.g., "at most k distinct" or "contains all characters of target"). Map is more general but slightly more overhead.
How do I handle "exactly k" vs "at most k" problems?
For "at most k": direct sliding window, shrink when count exceeds k. For "exactly k": either (1) use atMost(k) - atMost(k-1) transformation, or (2) maintain two windows—one with at most k, one with at most k-1—simultaneously. The transformation approach is cleaner.
Why doesn't variable sliding window work with negative numbers?
For sum problems, the window logic assumes: "if current sum is too large, shrinking will reduce it." With negative numbers, adding an element might DECREASE the sum, and removing might INCREASE it. The monotonic property breaks. Use prefix sums + binary search or monotonic deque instead.
What's the difference between shrinking for "longest" vs "shortest"?
For "longest": shrink while window is INVALID, trying to restore validity. Then update max. You want the biggest valid window. For "shortest": shrink while window is VALID, recording each valid state. You want the smallest window that still satisfies the requirement. The while condition is inverted.