Dynamic and fixed-size windows over contiguous subarrays or substrings
Track a contiguous subsegment of an array or string by expanding a right boundary and lazily contracting a left boundary whenever a constraint is broken.
Core Invariant: Monotonicity invariant: As `right` expands, window validity only degrades; advancing `left` only restores validity. Left pointer never moves backward, guaranteeing O(N) total pointer steps.
Array contains negative numbers and constraint is on sum (monotonicity is broken; must use Prefix Sum + Hash Map).
from collections import defaultdict
def sliding_window_at_most_k(s: str, k: int) -> int:
counts = defaultdict(int)
left = 0
max_len = 0
for right in range(len(s)):
# 1. Expand window: include s[right]
counts[s[right]] += 1
# 2. Shrink window: contract from left while invalid
while len(counts) > k: # e.g., at most k distinct characters
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]] # Must remove key to fix len(counts)
left += 1
# 3. Window [left...right] is now guaranteed valid
max_len = max(max_len, right - left + 1)
return max_len# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #3 | Longest Substring Without Repeating Characters Hash TableStringSliding Window | Medium | 100% | 39.4% | ||
| #239 | Sliding Window Maximum ArrayQueueSliding WindowHeap (Priority Queue)Monotonic QueueRange Minimum/Maximum Query | Hard | 100% | 49.0% | ||
| #76 | Minimum Window Substring Hash TableStringSliding Window | Hard | 100% | 47.9% | ||
| #424 | Longest Repeating Character Replacement Hash TableStringSliding Window | Medium | 100% | 60.1% | ||
| #713 | Subarray Product Less Than K ArrayBinary SearchSliding WindowPrefix Sum | Medium | 100% | 0.5% | ||
| #1004 | Max Consecutive Ones III ArrayBinary SearchSliding WindowPrefix Sum | Medium | 88% | 0.7% | ||
| #658 | Find K Closest Elements ArrayTwo PointersBinary SearchSliding WindowSortingHeap (Priority Queue) | Medium | 88% | 0.5% | ||
| #567 | Permutation in String Hash TableTwo PointersStringSliding Window | Medium | 95% | 49.2% | ||
| #209 | Minimum Size Subarray Sum ArrayBinary SearchSliding WindowPrefix Sum | Medium | 88% | 52.2% | ||
| #1438 | Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit ArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue | Medium | 100% | 0.6% | ||
| #992 | Subarrays with K Different Integers ArrayHash TableSliding WindowCounting | Hard | 90% | 68.6% | ||
| #438 | Find All Anagrams in a String Hash TableStringSliding Window | Medium | 100% | 54.1% | ||
| #485 | Max Consecutive Ones Array | Easy | 89% | 65.6% | ||
| #219 | Contains Duplicate II ArrayHash TableSliding Window | Easy | 78% | 51.5% | ||
| #340 | Longest Substring with At Most K Distinct Characters Hash TableStringSliding Window | Medium | 100% | 50.1% | ||
| #1423 | Maximum Points You Can Obtain from Cards ArraySliding WindowPrefix Sum | Medium | 100% | 0.6% | ||
| #904 | Fruit Into Baskets ArrayHash TableSliding Window | Medium | 74% | 0.5% | ||
| #1838 | Frequency of the Most Frequent Element ArrayBinary SearchGreedySliding WindowSortingPrefix Sum | Medium | 100% | 45.0% | ||
| #643 | Maximum Average Subarray I ArraySliding Window | Easy | 100% | 48.4% | ||
| #480 | Sliding Window Median ArrayHash TableSliding WindowHeap (Priority Queue)Treap | Hard | 69% | 39.0% | ||
| #632 | Smallest Range Covering Elements from K Lists ArrayHash TableGreedySliding WindowSortingHeap (Priority Queue) | Hard | 100% | 70.2% | ||
| #2444 | Count Subarrays With Fixed Bounds ArrayQueueSliding WindowMonotonic Queue | Hard | 88% | 69.2% | ||
| #395 | Longest Substring with At Least K Repeating Characters Hash TableStringDivide and ConquerSliding Window | Medium | 100% | 46.4% | ||
| #30 | Substring with Concatenation of All Words Hash TableStringSliding Window | Hard | 95% | 34.7% | ||
| #1248 | Count Number of Nice Subarrays ArrayHash TableMathSliding WindowPrefix Sum | Medium | 92% | 75.4% | ||
| #2134 | Minimum Swaps to Group All 1's Together II ArraySliding Window | Medium | 75% | 65.7% | ||
| #2461 | Maximum Sum of Distinct Subarrays With Length K ArrayHash TableSliding Window | Medium | 63% | 43.2% | ||
| #862 | Shortest Subarray with Sum at Least K ArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic Queue | Hard | 100% | 32.9% | ||
| #1297 | Maximum Number of Occurrences of a Substring Hash TableStringSliding Window | Medium | 75% | 54.6% | ||
| #1052 | Grumpy Bookstore Owner ArraySliding Window | Medium | 100% | 64.1% | ||
| #1493 | Longest Subarray of 1's After Deleting One Element ArrayDynamic ProgrammingSliding Window | Medium | 100% | 71.3% | ||
| #413 | Arithmetic Slices ArrayDynamic ProgrammingSliding Window | Medium | 100% | 64.8% | ||
| #930 | Binary Subarrays With Sum ArrayHash TableSliding WindowPrefix Sum | Medium | 89% | 0.7% | ||
| #220 | Contains Duplicate III ArraySliding WindowSortingBucket SortOrdered Set | Hard | 88% | 24.9% | ||
| #2537 | Count the Number of Good Subarrays ArrayHash TableSliding Window | Medium | 50% | 65.7% | ||
| #2958 | Length of Longest Subarray With at Most K Frequency ArrayHash TableSliding Window | Medium | 100% | 0.6% | ||
| #3208 | Alternating Groups II ArraySliding Window | Medium | 100% | 60.0% | ||
| #1695 | Maximum Erasure Value ArrayHash TableSliding Window | Medium | 100% | 64.4% | ||
| #1876 | Substrings of Size Three with Distinct Characters Hash TableStringSliding WindowCounting | Easy | 100% | 76.9% | ||
| #187 | Repeated DNA Sequences Hash TableStringBit ManipulationSliding WindowRolling HashHash FunctionZ AlgorithmBoyer–Moore String-Search Algorithm | Medium | 88% | 53.6% | ||
| #1044 | Longest Duplicate Substring StringBinary SearchSliding WindowRolling HashSuffix ArrayHash FunctionSuffix AutomatonSuffix TreeZ AlgorithmBoyer–Moore String-Search Algorithm | Hard | 88% | 31.3% | ||
| #3090 | Maximum Length Substring With Two Occurrences Hash TableStringSliding Window | Easy | 88% | 0.8% | ||
| #718 | Maximum Length of Repeated Subarray ArrayBinary SearchDynamic ProgrammingSliding WindowRolling HashHash Function | Medium | 88% | 51.5% | ||
| #1358 | Number of Substrings Containing All Three Characters Hash TableStringSliding Window | Medium | 75% | 74.4% | ||
| #2009 | Minimum Number of Operations to Make Array Continuous ArrayHash TableBinary SearchSliding Window | Hard | 69% | 0.5% | ||
| #1652 | Defuse the Bomb ArraySliding Window | Easy | 67% | 0.8% | ||
| #689 | Maximum Sum of 3 Non-Overlapping Subarrays ArrayDynamic ProgrammingSliding WindowPrefix Sum | Hard | 63% | 0.6% | ||
| #1343 | Medium | 50% | 73.4% | |||
| #1839 | Longest Substring Of All Vowels in Order StringSliding Window | Medium | 100% | 0.5% | ||
| #2401 | Longest Nice Subarray ArrayBit ManipulationSliding Window | Medium | 100% | 64.8% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Dynamic and fixed-size windows over contiguous subarrays or substrings It is categorized under Fundamentals and features 147 curated interview problems across Easy (16), Medium (93), and Hard (38) difficulties.
Companies frequently asking Sliding Window questions include Google, Amazon, Meta, Microsoft, Bloomberg, TikTok.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.