Group 1: Fixed-Size Sliding Window
This group focuses on the simplest form of sliding windows, where the size is fixed. These problems introduce the core concepts of maintaining a sum or count within a window of a specific size.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 1 | Substrings of Size Three with Distinct Characters | Link | Fixed-Size Window | Base case. The simplest form of a fixed-size window. You check a trivial condition within a window of size 3. | |
| 2 | Maximum Average Subarray I | Link | Fixed-Size Window (Sum) | Introduces the core optimization: add the new element and subtract the old one to efficiently update the window's sum. | |
| 3 | Maximum Number of Vowels in a Substring of Given Length | Link | Fixed-Size Window (Count) | Boring variation of the previous problem. Instead of updating a sum, you update a count based on a condition (is_vowel). | |
| 4 | Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold | Link | Fixed-Size Window (Sum + Condition) | Builds on the fixed-size sum pattern by adding a simple check against a threshold in each step. | |
| 5 | Permutation in String | Link | Fixed-Size Window + Frequency Map | Introduces using a frequency map (or array) to track the state of the window, comparing it against a target map. | |
| 6 | Find All Anagrams in a String | Link | Fixed-Size Window + Frequency Map | Boring variation. Identical logic to Permutation in String, but you collect all valid starting indices instead of returning true/false. | |
| 7 | Repeated DNA Sequences | Link | Fixed-Size Window + Set | Uses a fixed window (size 10) and a hash set to keep track of substrings that have already been seen. | |
| 8 | K-Radius Subarray Averages | Link | Fixed-Size Window + Prefix Sum | Uses a window of size 2k+1. The core is calculating the sum efficiently, reinforcing the standard fixed-window sum pattern. |
Group 2: Dynamic-Size Sliding Window (The Core Pattern)
This group introduces the more powerful dynamic-size sliding windows, where the window can expand and contract based on conditions. These problems are the most common and useful in practice.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 9 | Contains Duplicate II | Link | Dynamic Window + Set | Base case for dynamic windows. Introduces maintaining a window of at most size k to check for nearby duplicates using a hash set. | |
| 10 | Longest Substring Without Repeating Characters | Link | Dynamic Window + Set | The canonical dynamic window problem. The window expands to the right and shrinks from the left when a repeat is found. | |
| 11 | Fruit Into Baskets | Link | Dynamic Window + Map | Boring variation of the above. The condition changes from 'all unique' to 'at most 2 unique,' requiring a frequency map instead of a set. | |
| 12 | Minimum Size Subarray Sum | Link | Dynamic Window (Shrinking) | A classic twist. The goal is to find the smallest valid window, so you expand until valid, then shrink as much as possible. | |
| 13 | Subarray Product Less Than K | Link | Dynamic Window (Counting) | Conceptual leap. Introduces counting all valid subarrays. The key insight is that if a window is valid, so are all its subarrays ending at the right pointer. | |
| 14 | Get Equal Substrings Within Budget | Link | Dynamic Window (Cost Calculation) | The 'cost' of including an element is now variable (abs(s[i] - t[i])), making the window condition more dynamic than a simple count. | |
| 15 | Longest Subarray of 1's After Deleting One Element | Link | Dynamic Window (At Most K) | A classic 'at most K' problem where K=1. The window can contain at most one zero. | |
| 16 | Max Consecutive Ones III | Link | Dynamic Window (At Most K) | Generalizes the previous problem. The window can contain at most k zeros. | |
| 17 | Maximize the Confusion of an Exam | Link | Dynamic Window (At Most K) | Boring variation. Solves the 'at most k F's' and 'at most k T's' problems and takes the max, reinforcing the Max Consecutive Ones III pattern. | |
| 18 | Longest Nice Substring | Link | Brute-Force Window (or D&C) | While solvable with a sliding window, a brute-force check of all substrings is simpler and often accepted. Introduces checking a complex window property. |
Group 3: Advanced Windows & Counting Subarrays
Here we explore more advanced sliding window techniques, including counting subarrays and managing complex conditions. These problems require a deeper understanding of how to manipulate the window and track state effectively.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 19 | Number of Substrings Containing All Three Characters | Link | Dynamic Window (Counting) | Builds on the counting logic from Subarray Product Less Than K. Once the window is valid, you add 1 + left_pointer_pos to the count. | |
| 20 | Binary Subarrays with Sum | Link | Sliding Window (At-Most-K Trick) | Introduces a powerful sub-pattern: solving for exactly K by computing atMost(K) - atMost(K-1). A significant step in abstract thinking. | |
| 21 | Count Number of Nice Subarrays | Link | Sliding Window (At-Most-K Trick) | Boring variation of Binary Subarrays with Sum. Reinforces the at-most-K trick by replacing 'sum' with 'count of odd numbers.' | |
| 22 | Longest Repeating Character Replacement | Link | Dynamic Window (Abstract Condition) | A classic, challenging window problem. The validity condition (window_len - max_freq <= k) is abstract and requires tracking extra state (max frequency). | |
| 23 | Maximum Erasure Value | Link | Dynamic Window + Set & Sum | Combines the 'unique characters' window from problem #10 with the need to efficiently track the window's sum. | |
| 24 | Longest Turbulent Subarray | Link | Dynamic Window (Stateful Condition) | The validity of the window depends on the relationship between the last two elements, requiring stateful checks inside the loop. | |
| 25 | Grumpy Bookstore Owner | Link | Fixed Window (Gain Calculation) | A clever application of a fixed window. First, calculate the base satisfaction, then slide a window of size minutes to find the maximum additional satisfaction possible. | |
| 26 | Frequency of the Most Frequent Element | Link | Dynamic Window (After Sorting) | A difficult problem that becomes a sliding window after sorting. The condition k + sum >= window_len * arr[right] is non-obvious and a big step up. | |
| 27 | Longest Continuous Subarray with Absolute Diff Less Than or Equal to Limit | Link | Dynamic Window + Deques | Major conceptual leap. Requires using two deques to maintain the min and max of the current window in O(1) time, a very advanced window management technique. |
Group 4: Inverted & Multi-Pass Windows
This topic explores problems that require a different perspective on sliding windows, such as inverted windows or multi-pass approaches. These problems often involve clever re-framing of the problem to fit the sliding window paradigm.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 28 | Maximum Points You can Obtain from Cards | Link | Inverted Sliding Window | Introduces a clever re-framing: finding the max sum of k ends is equivalent to finding the min sum of a middle subarray of size n-k. | |
| 29 | Minimum Operations to Reduce X to Zero | Link | Inverted Sliding Window | Boring variation of the previous problem. The logic is identical: re-frame it as finding the longest middle subarray with a target sum. | |
| 30 | Replace the Substring for Balanced String | Link | Inverted Window + Frequency Map | A complex variation. Find the minimum window that, when replaced, can balance the counts of the entire string. Requires pre-calculating counts. | |
| 31 | Maximum Sum of Two Non-Overlapping Subarrays | Link | Multi-Pass Sliding Window | A multi-step problem. Requires multiple passes to calculate prefix/suffix maxes for one subarray length, then iterate to find the best combination with the second. | |
| 32 | Find Two Non-Overlapping Sub-arrays Each with Target Sum | Link | DP + Sliding Window | Best solved by finding all valid subarrays first, then using DP to find the best non-overlapping pair. The 'window' part is finding the subarrays. |
Group 5: Problems Combining Sliding Window with Other Major Patterns
Finally we explore problems that cleverly combine sliding windows with other major patterns, such as BFS or dynamic programming. These problems often require a hybrid approach and are more complex.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 33 | Maximum Length of Repeated Subarray | Link | Dynamic Programming (Not Sliding Window) | This is a classic 2D DP problem. The 'sliding' aspect is superficial; a direct DP solution is standard and more intuitive. | |
| 34 | Longest Substring with At Least K Repeating Characters | Link | Divide and Conquer (Recursive Window) | Standard sliding window fails here. The optimal solution uses a recursive 'divide and conquer' approach, splitting the string by invalid characters. | |
| 35 | Contains Duplicate III | Link | Window + Bucketing / Balanced BST | A very advanced problem. Requires a window combined with either a balanced BST or a clever 'bucketing' system to check the value condition efficiently. | |
| 36 | Jump Game VI | Link | DP + Sliding Window (Deque) | A dynamic programming problem where a sliding window (managed by a deque) is used to optimize the state transition, finding the max score in the last k steps. | |
| 37 | New 21 Game | Link | DP + Sliding Window (Sum) | A probability DP problem. A sliding window is used as a mathematical trick to keep a running sum of probabilities, simplifying the DP calculation from O(N*K) to O(N). | |
| 38 | Longest Substring of All Vowels in Order | Link | Two Pointers (State Machine) | More of a state machine approach with two pointers than a classic sliding window. The window only advances or resets based on strict ordering rules. | |
| 39 | Swap for Longest Repeated Character Substring | Link | Multi-Pass + Window | Complex logic. Requires pre-calculating group sizes, then iterating through each group and using a window-like approach to see if it can be extended by one swap. | |
| 40 | Maximum Number of Occurrences of a Substring | Link | Brute-Force Window | Due to tight constraints on length (minSize, maxSize), you can iterate through all possible substrings and validate them, making it a brute-force application of windows. |