← All patterns
Sliding Window
Maintain a window (contiguous subarray/substring) that expands and contracts, tracking a running property, to avoid recomputation.
When to use it
- Longest/shortest contiguous substring or subarray satisfying a condition.
- Fixed-size window aggregate (max sum of size-k subarray).
- Problems with 'contiguous' and 'at most/exactly K distinct' phrasing.
Signals in the problem statement
- Keywords: substring, subarray, contiguous, window, at most K, longest/shortest.
- Brute force would recompute overlapping work for every window position.
Common pitfalls
- Shrinking the window incorrectly (should shrink from the left while the condition is violated, not just once).
- Using a frequency map but forgetting to remove entries at 0 count, corrupting 'distinct count' logic.
Practice Problems
Longest Substring Without Repeating Characters
MediumAsked at: Amazon, Bloomberg, Adobe
Given a string, find the length of the longest substring without repeating characters.
Time: O(n) · Space: O(min(n, alphabet size))
Minimum Window Substring
HardAsked at: Meta, Google, Uber
Given strings s and t, return the smallest substring of s containing every character of t (with multiplicity).
Time: O(n + m) · Space: O(alphabet size)