Sliding Window
Phase 1 18 solutionsSliding Window
mindmap
root((Sliding Window))
Fixed Window
Permutation In String LC567
Contains Duplicate II LC219
Maximum Points from Cards LC1423
Variable Window Shrinkable
Minimum Size Subarray Sum LC209
Minimum Window Substring LC76
Longest Substring Without Repeating Characters LC3
Max Consecutive Ones III LC1004
Fruit Into Baskets LC904
Longest Substring K Distinct LC340
Frequency Tracking
Longest Repeating Character Replacement LC424
Permutation In String LC567
Number of Substrings All Three LC1358
Monotonic Deque
Sliding Window Maximum LC239
atMost Trick (Exact Count)
Binary Subarrays With Sum LC930
Count Nice Subarrays LC1248
Subarrays K Different Integers LC992
Subsequence Window
Minimum Window Subsequence LC727
Other
Best Time to Buy And Sell Stock LC121
Find K Closest Elements LC658
Problem List
Mermaid Diagrams
1. When to Use Sliding Window
flowchart TD
A["Problem involves contiguous subarray/substring?"] -->|No| B[Not sliding window]
A -->|Yes| C[Is window size fixed?]
C -->|Yes| D["Fixed Window<br/>LC 567, LC 219"]
C -->|No| E["Need to find min/max window?"]
E -->|Min window meeting condition| F["Shrinkable Window<br/>LC 76, LC 209"]
E -->|Max window meeting condition| G["Expandable Window<br/>LC 3, LC 424"]
E -->|Max in each window| H["Monotonic Deque<br/>LC 239"]
2. Fixed vs Variable Window Decision Tree
flowchart TD
A["Subarray/Substring Problem"] --> B{Window size given?}
B -->|Yes - size k| C[Fixed Window]
B -->|No| D{Optimize for?}
C --> C1["Slide: remove left, add right<br/>Maintain window invariant"]
D -->|Minimum length| E["Variable - Shrink when valid<br/>LC 76, LC 209"]
D -->|Maximum length| F["Variable - Shrink when invalid<br/>LC 3, LC 424"]
D -->|Max element per window| G["Monotonic Deque<br/>LC 239"]
3. Expand/Shrink Window Pattern Flow
flowchart LR
A(["Start<br/>l=0, r=0"]) --> B[Expand: add arr-r to window]
B --> C{Window valid?}
C -->|Yes| D[Update answer]
D --> E[r++]
E --> B
C -->|No - shrink needed| F["Remove arr-l from window<br/>l++"]
F --> C
E --> G{r == n?}
G -->|Yes| H([Return answer])
G -->|No| B
4. Monotonic Deque Pattern (LC 239)
flowchart TD
A[New element arr-i] --> B{"Deque not empty AND<br/>deque.back <= arr-i?"}
B -->|Yes - pop smaller| C[deque.pop_back]
C --> B
B -->|No| D[deque.push_back index i]
D --> E{"deque.front out of window?<br/>front < i - k + 1"}
E -->|Yes| F[deque.pop_front]
F --> E
E -->|No| G[Window max = arr-deque.front]
G --> H[Append to result if i >= k-1]
Complexity Summary
| Problem | Time | Space | Pattern |
|---|---|---|---|
| contains_duplicate_ii | O(n) | O(k) | Hash set fixed window |
| best_time_to_buy_and_sell_stock | O(n) | O(1) | Min tracking |
| longest_substring_without_repeating_characters | O(n) | O(min(n,m)) | Shrink on duplicate |
| longest_repeating_character_replacement | O(n) | O(1) | Max freq tracking |
| permutation_in_string | O(n) | O(1) | Fixed window freq match |
| minimum_size_subarray_sum | O(n) | O(1) | Shrink when sum ≥ target |
| find_k_closest_elements | O(log n) | O(1) | Binary search left boundary |
| minimum_window_substring | O(n) | O(m+n) | Two counters: need/have |
| sliding_window_maximum | O(n) | O(k) | Monotonic decreasing deque |
| max_consecutive_ones_iii | O(n) | O(1) | Shrinkable window (k zeros) |
| fruit_into_baskets | O(n) | O(1) | Variable window + hashmap |
| binary_subarrays_with_sum | O(n) | O(n) | atMost trick |
| count_number_of_nice_subarrays | O(n) | O(n) | atMost trick |
| number_of_substrings_containing_all_three_characters | O(n) | O(1) | Frequency tracking |
| maximum_points_you_can_obtain_from_cards | O(k) | O(1) | Fixed window (complement) |
| longest_substring_with_at_most_k_distinct_characters | O(n) | O(k) | Variable window + hashmap |
| subarrays_with_k_different_integers | O(n) | O(n) | atMost trick |
| minimum_window_subsequence | O(m·n) | O(1) | Two-pointer subsequence |
Study Order
flowchart LR
subgraph S1["Stage 1: Easy"]
sw1["best_time_stock(121) → contains_duplicate_ii(219)"]
sw2["longest_substr_no_repeat(3)"]
end
subgraph S2["Stage 2: Variable Window"]
sw3["max_consecutive_ones_iii(1004) → fruit_into_baskets(904)"]
sw4["longest_substr_k_distinct(340) → minimum_size_subarray_sum(209)"]
sw5["longest_repeating_replacement(424)"]
end
subgraph S3["Stage 3: Fixed Window + atMost Trick"]
sw6["permutation_in_string(567) → maximum_points_from_cards(1423)"]
sw7["find_k_closest_elements(658) → binary_subarrays_with_sum(930)"]
sw8["count_nice_subarrays(1248) → subarrays_k_different(992)"]
sw9["number_of_substrings_all_three(1358)"]
end
subgraph S4["Stage 4: Hard"]
sw10["minimum_window_substring(76) → sliding_window_maximum(239)"]
sw11["minimum_window_subsequence(727)"]
end
S1 --> S2 --> S3 --> S4
Recommended order: Easy fixed → Easy variable → Medium fixed → Medium variable → Hard
Sliding Window — Pattern Notes
Core Intuition
Sliding window converts O(n²) brute force (check every subarray) into O(n) by maintaining a window that expands and contracts. The key question: when do I shrink the window?
- Fixed window: Window size is given. Slide by adding right element and removing left element.
- Variable window (find max): Expand right freely, shrink left when constraint is violated.
- Variable window (find min): Expand right until constraint is met, then shrink left as much as possible.
- Frequency tracking: Use a hashmap/array to track character counts inside the window.
- Monotonic deque: For window maximum/minimum — maintain a deque of useful candidates.
Decision Flowchart
flowchart TD
A[Sliding Window Problem] --> B{Window size fixed?}
B -- Yes --> C["Fixed window<br/>Add right, remove left at each step"]
B -- No --> D{Minimize or Maximize?}
D -- Maximize --> E["Expand right freely<br/>Shrink left when invalid<br/>Track max valid window"]
D -- Minimize --> F["Expand until valid<br/>Shrink left while still valid<br/>Track min window size"]
E --> G{"Need element ordering<br/>in window?"}
G -- Yes --> H[Monotonic Deque]
G -- No --> I["HashMap / frequency array"]
F --> I
Per-Problem Notes
1. Contains Duplicate II — LC 219 | Easy
- Key insight: Fixed window of size k. Use a HashSet. If adding element already in set → True. Remove
nums[i-k]when window exceeds k. - Tricky: Window size is k, so remove element at
i-k(noti-k-1). - Common mistakes: Off-by-one in window removal. Using hashmap instead of hashset (overkill).
- Time: O(n) | Space: O(k)
2. Best Time to Buy/Sell Stock — LC 121 | Easy
- Key insight: Track running minimum (buy price). For each day, profit = price - min_so_far. Track max profit.
- Tricky: This is technically a sliding window where left = min price day, right = current day.
- Common mistakes: Updating max profit before updating min price. Allowing sell before buy.
- Time: O(n) | Space: O(1)
3. Longest Substring Without Repeating Characters — LC 3 | Medium
- Key insight: Variable window. HashMap stores last seen index of each char. When duplicate found, move left to
max(left, last_seen[char] + 1). - Tricky: Move left to
max(left, ...)— don't move left backward if the duplicate is outside current window. - Common mistakes: Moving left to
last_seen[char] + 1without the max → left can move backward. - Time: O(n) | Space: O(min(n, 26))
4. Longest Repeating Character Replacement — LC 424 | Medium
- Key insight: Window is valid if
window_size - max_freq <= k. Expand right, track max frequency of any char. Shrink left when invalid. - Tricky:
max_freqnever decreases (only update when new char beats it). This is a subtle optimization — we only care about windows larger than the best seen. - Common mistakes: Recalculating max_freq when shrinking (O(26) per step, still O(n) total but unnecessary). Not understanding why max_freq doesn't need to decrease.
- Time: O(n) | Space: O(26) = O(1)
5. Permutation in String — LC 567 | Medium
- Key insight: Fixed window of size
len(s1). Compare frequency arrays of window and s1. Slide window across s2. - Tricky: Compare 26-element arrays at each step. Or track a
matchescounter (number of chars with equal frequency). - Common mistakes: Sorting window at each step (O(n·k log k)). Not using fixed window size.
- Time: O(n) | Space: O(26) = O(1)
6. Minimum Size Subarray Sum — LC 209 | Medium
- Key insight: Variable window (minimize). Expand right, shrink left while
sum >= target. Track min length. - Tricky: Shrink as much as possible while constraint is still satisfied.
- Common mistakes: Shrinking only once per right expansion. Not handling case where no valid subarray exists (return 0).
- Time: O(n) | Space: O(1)
7. K Closest Elements — LC 658 | Medium
- Key insight: Binary search for the left boundary of the window of size k. Compare
x - arr[mid]vsarr[mid+k] - xto decide which side to keep. - Tricky: Binary search on the left index, not on the value. Condition:
x - arr[mid] > arr[mid+k] - x→ move left right. - Common mistakes: Binary searching on value instead of index. Wrong comparison direction.
- Time: O(log(n-k) + k) | Space: O(1)
8. Minimum Window Substring — LC 76 | Hard
- Key insight: Variable window (minimize). Expand right until all chars of t are covered. Then shrink left while still valid. Track min window.
- Tricky: Use
haveandneedcounters.haveincrements only when a char's count in window matches its count in t. - Common mistakes: Incrementing
havefor every occurrence instead of only when count matches. Not handling chars not in t. - Time: O(n + m) | Space: O(n + m)
9. Sliding Window Maximum — LC 239 | Hard
- Key insight: Monotonic decreasing deque stores indices. Front of deque is always the max of current window. Remove indices outside window from front. Remove smaller elements from back before adding new element.
- Tricky: Store indices (not values) in deque to check if front is outside window. Remove from back while
nums[deque[-1]] <= nums[i]. - Common mistakes: Storing values instead of indices (can't check window boundary). Not removing out-of-window indices from front.
- Time: O(n) | Space: O(k)
Edge Cases to Watch For
- Empty string/array: Return 0 or "" immediately.
- Window larger than array: k > n — return entire array or handle gracefully.
- All same characters: Longest repeating replacement — entire string is valid if k ≥ 0.
- Target not achievable: Min window substring — return "" if t chars not all in s. Min subarray sum — return 0 if no valid subarray.
- Single character strings: Permutation in string — trivially check if s1 char is in s2.
- Negative numbers: Sliding window generally doesn't work with negatives for sum problems (use prefix sum + hashmap instead).
- Duplicate characters in t: Min window substring — must match counts, not just presence.
- k = 0: Contains Dup II — only exact same index duplicates count (impossible), return False.
Best Time To Buy And Sell Stock ▼ expand
from typing import List
class Solution:
"""
## 121. Best Time to Buy and Sell Stock
You are given an array `prices` where `prices[i]` is the price of a given stock on
the `i`-th day. You want to maximize your profit by choosing a single day to buy one
stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot
achieve any profit, return `0`.
### Examples
```text
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price=1), sell on day 5 (price=6), profit = 6-1 = 5.
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: No profitable transaction possible.
```
### Constraints
- `1 <= prices.length <= 10^5`
- `0 <= prices[i] <= 10^4`
"""
def maxProfit_brute(self, prices: List[int]) -> int:
# Try every buy-sell pair — O(n^2)
# O(n^2) time, O(1) space
max_p = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
max_p = max(max_p, prices[j] - prices[i])
return max_p
def maxProfit(self, prices: List[int]) -> int:
# Track the minimum price seen so far as the best buy day
# At each price, compute profit if we sold today; update best
# O(n) time, O(1) space
min_price, max_p = float("inf"), 0
for price in prices:
min_price = min(min_price, price)
max_p = max(max_p, price - min_price)
return max_p
if __name__ == "__main__":
sol = Solution()
assert sol.maxProfit([7, 1, 5, 3, 6, 4]) == 5
assert sol.maxProfit([7, 6, 4, 3, 1]) == 0
assert sol.maxProfit([1, 2]) == 1
assert sol.maxProfit_brute([7, 1, 5, 3, 6, 4]) == 5
assert sol.maxProfit_brute([7, 6, 4, 3, 1]) == 0
print("All tests passed.")Binary Subarrays With Sum ▼ expand
"""
LC 930 - Binary Subarrays With Sum
Given a binary array nums and an integer goal, return the number of
non-empty subarrays with a sum equal to goal.
Examples:
```text
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Input: nums = [0,0,0,0,0], goal = 0
Output: 15
```
Constraints:
- 1 <= nums.length <= 3 * 10^4
- nums[i] is either 0 or 1
- 0 <= goal <= nums.length
"""
from typing import List
from collections import defaultdict
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
# Approach 1: prefix sum + hash map
# count[prefix] = how many times this prefix sum has appeared
count = defaultdict(int)
count[0] = 1
prefix = 0
result = 0
for num in nums:
prefix += num
# subarrays ending here with sum == goal
result += count[prefix - goal]
count[prefix] += 1
return result
def numSubarraysWithSum_atmost(self, nums: List[int], goal: int) -> int:
# Approach 2: atMost(goal) - atMost(goal-1)
# The atMost trick converts exact-count to two atMost calls
def atMost(g: int) -> int:
if g < 0:
return 0
left = curr_sum = res = 0
for right in range(len(nums)):
curr_sum += nums[right]
# shrink window until sum <= g
while curr_sum > g:
curr_sum -= nums[left]
left += 1
# all subarrays ending at right with sum <= g
res += right - left + 1
return res
return atMost(goal) - atMost(goal - 1)
if __name__ == '__main__':
s = Solution()
assert s.numSubarraysWithSum([1,0,1,0,1], 2) == 4
assert s.numSubarraysWithSum([0,0,0,0,0], 0) == 15
assert s.numSubarraysWithSum_atmost([1,0,1,0,1], 2) == 4
assert s.numSubarraysWithSum_atmost([0,0,0,0,0], 0) == 15
print("All tests passed.")Contains Duplicate Ii ▼ expand
from typing import List
class Solution:
"""
## 219. Contains Duplicate II
Given an integer array `nums` and an integer `k`, return `true` if there exist two
distinct indices `i` and `j` in the array such that `nums[i] == nums[j]` and
`abs(i - j) <= k`.
### Examples
```text
Input: nums = [1, 2, 3, 1], k = 3
Output: true
Input: nums = [1, 0, 1, 1], k = 1
Output: true
Input: nums = [1, 2, 3, 1, 2, 3], k = 2
Output: false
```
### Constraints
- `1 <= nums.length <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- `0 <= k <= 10^5`
"""
def containsNearbyDuplicate_brute(self, nums: List[int], k: int) -> bool:
# For each element, check the next k elements for a duplicate — O(n*k)
# O(n * k) time, O(1) space
for i in range(len(nums)):
for j in range(i + 1, min(i + k + 1, len(nums))):
if nums[i] == nums[j]:
return True
return False
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# Maintain a sliding set of size k; if new element already in set, found duplicate
# Remove the element that just fell out of the window (nums[i-k])
# O(n) time, O(k) space
window = set()
for i, num in enumerate(nums):
if num in window:
return True
window.add(num)
if len(window) > k:
window.remove(nums[i - k])
return False
if __name__ == "__main__":
sol = Solution()
assert sol.containsNearbyDuplicate([1, 2, 3, 1], 3) == True
assert sol.containsNearbyDuplicate([1, 0, 1, 1], 1) == True
assert sol.containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2) == False
assert sol.containsNearbyDuplicate_brute([1, 2, 3, 1], 3) == True
assert sol.containsNearbyDuplicate_brute([1, 2, 3, 1, 2, 3], 2) == False
print("All tests passed.")Count Number Of Nice Subarrays ▼ expand
"""
LC 1248 - Count Number of Nice Subarrays
Given an array of integers nums and an integer k, return the number of
nice sub-arrays. A subarray is nice if there are k odd numbers in it.
Examples:
```text
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Input: nums = [2,4,6], k = 1
Output: 0
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
```
Constraints:
- 1 <= nums.length <= 5 * 10^4
- 1 <= nums[i] <= 10^5
- 1 <= k <= nums.length
"""
from typing import List
from collections import defaultdict
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
# Approach 1: prefix sum
# Treat odd as 1, even as 0 — same as binary subarrays with sum k
count = defaultdict(int)
count[0] = 1
prefix = 0
result = 0
for num in nums:
prefix += num % 2 # 1 if odd, 0 if even
result += count[prefix - k]
count[prefix] += 1
return result
def numberOfSubarrays_atmost(self, nums: List[int], k: int) -> int:
# Approach 2: atMost(k) - atMost(k-1)
# exactly(k) = atMost(k) - atMost(k-1)
def atMost(limit: int) -> int:
left = odds = res = 0
for right in range(len(nums)):
odds += nums[right] % 2
while odds > limit:
odds -= nums[left] % 2
left += 1
res += right - left + 1
return res
return atMost(k) - atMost(k - 1)
if __name__ == '__main__':
s = Solution()
assert s.numberOfSubarrays([1,1,2,1,1], 3) == 2
assert s.numberOfSubarrays([2,4,6], 1) == 0
assert s.numberOfSubarrays([2,2,2,1,2,2,1,2,2,2], 2) == 16
assert s.numberOfSubarrays_atmost([1,1,2,1,1], 3) == 2
assert s.numberOfSubarrays_atmost([2,2,2,1,2,2,1,2,2,2], 2) == 16
print("All tests passed.")Find K Closest Elements ▼ expand
from typing import List
import bisect
class Solution:
"""
## 658. Find K Closest Elements
Given a sorted integer array `arr`, two integers `k` and `x`, return the `k`
closest integers to `x` in the array. The result should also be sorted in ascending
order.
An integer `a` is closer to `x` than an integer `b` if:
- `|a - x| < |b - x|`, or
- `|a - x| == |b - x|` and `a < b`
### Examples
```text
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Input: arr = [1, 2, 3, 4, 5], k = 4, x = -1
Output: [1, 2, 3, 4]
```
### Constraints
- `1 <= k <= arr.length <= 10^4`
- `arr` is sorted in ascending order.
- `-10^4 <= arr[i], x <= 10^4`
"""
def findClosestElements_sort(self, arr: List[int], k: int, x: int) -> List[int]:
# Sort by distance to x, take first k, then re-sort for ascending order
# O(n log n) time, O(n) space
return sorted(sorted(arr, key=lambda a: (abs(a - x), a))[:k])
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# Binary search for the left boundary of the k-element window
# Compare distance of left edge vs right edge: x-arr[mid] vs arr[mid+k]-x
# Move window right if left edge is farther from x than right edge
# O(log n + k) time, O(1) space
lo, hi = 0, len(arr) - k
while lo < hi:
mid = (lo + hi) // 2
if x - arr[mid] > arr[mid + k] - x:
lo = mid + 1
else:
hi = mid
return arr[lo:lo + k]
if __name__ == "__main__":
sol = Solution()
assert sol.findClosestElements([1, 2, 3, 4, 5], 4, 3) == [1, 2, 3, 4]
assert sol.findClosestElements([1, 2, 3, 4, 5], 4, -1) == [1, 2, 3, 4]
assert sol.findClosestElements([1, 2, 3, 4, 5], 4, 10) == [2, 3, 4, 5]
assert sol.findClosestElements_sort([1, 2, 3, 4, 5], 4, 3) == [1, 2, 3, 4]
assert sol.findClosestElements_sort([1, 2, 3, 4, 5], 4, -1) == [1, 2, 3, 4]
print("All tests passed.")Fruit Into Baskets ▼ expand
"""
LC 904 - Fruit Into Baskets
You have two baskets, and each basket can carry any quantity of fruit, but
you want each basket to only carry one type of fruit. Given an integer array
fruits where fruits[i] is the type of fruit the ith tree produces, return the
maximum number of fruits you can pick (must pick from a contiguous subarray).
Equivalent to: longest subarray with at most 2 distinct values.
Examples:
```text
Input: fruits = [1,2,1]
Output: 3
Input: fruits = [0,1,2,2]
Output: 3
Input: fruits = [1,2,3,2,2]
Output: 4
```
Constraints:
- 1 <= fruits.length <= 10^5
- 0 <= fruits[i] < fruits.length
"""
from typing import List
from collections import defaultdict
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
# Sliding window with freq map — at most 2 distinct fruit types
count = defaultdict(int)
left = 0
result = 0
for right in range(len(fruits)):
count[fruits[right]] += 1
# More than 2 distinct types — shrink window from left
while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1
result = max(result, right - left + 1)
return result
if __name__ == '__main__':
s = Solution()
assert s.totalFruit([1,2,1]) == 3
assert s.totalFruit([0,1,2,2]) == 3
assert s.totalFruit([1,2,3,2,2]) == 4
assert s.totalFruit([3,3,3,1,2,1,1,2,3,3,4]) == 5
print("All tests passed.")Longest Repeating Character Replacement ▼ expand
class Solution:
"""
## 424. Longest Repeating Character Replacement
You are given a string `s` and an integer `k`. You can choose any character of the
string and change it to any other uppercase English character. You can perform this
operation at most `k` times.
Return the length of the longest substring containing the same letter you can get
after performing the above operations.
### Examples
```text
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with 'B's or vice versa.
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' -> "AABBBBA" (length 4).
```
### Constraints
- `1 <= s.length <= 10^5`
- `s` consists of only uppercase English letters.
- `0 <= k <= s.length`
"""
def characterReplacement_brute(self, s: str, k: int) -> int:
# Try all windows; window is valid if (size - max_freq) <= k — O(n^2)
# O(n^2) time, O(1) space
best = 0
for i in range(len(s)):
freq: dict[str, int] = {}
for j in range(i, len(s)):
freq[s[j]] = freq.get(s[j], 0) + 1
window = j - i + 1
if window - max(freq.values()) <= k:
best = max(best, window)
return best
def characterReplacement(self, s: str, k: int) -> int:
# Expand right; window is valid if (size - max_freq) <= k replacements
# When invalid, slide left by 1 (shrink window, don't reset max_freq)
# max_freq only increases — we only care about windows larger than current best
# O(n) time, O(1) space
freq: dict[str, int] = {}
left = max_freq = best = 0
for right, ch in enumerate(s):
freq[ch] = freq.get(ch, 0) + 1
max_freq = max(max_freq, freq[ch])
window = right - left + 1
if window - max_freq > k:
freq[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
sol = Solution()
assert sol.characterReplacement("ABAB", 2) == 4
assert sol.characterReplacement("AABABBA", 1) == 4
assert sol.characterReplacement("A", 0) == 1
assert sol.characterReplacement_brute("ABAB", 2) == 4
assert sol.characterReplacement_brute("AABABBA", 1) == 4
print("All tests passed.")Longest Substring With At Most K Distinct Characters ▼ expand
"""
LC 340 - Longest Substring with At Most K Distinct Characters
Given a string s and an integer k, return the length of the longest
substring that contains at most k distinct characters.
Examples:
```text
Input: s = "eceba", k = 2
Output: 3
Input: s = "aa", k = 1
Output: 2
Input: s = "aabbcc", k = 2
Output: 4
```
Constraints:
- 1 <= s.length <= 5 * 10^4
- 0 <= k <= 50
"""
from collections import defaultdict
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
# Sliding window with freq map
# Expand right always, shrink left when distinct count > k
if k == 0:
return 0
count = defaultdict(int)
left = 0
result = 0
for right in range(len(s)):
count[s[right]] += 1
# Too many distinct chars — shrink from left
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
result = max(result, right - left + 1)
return result
if __name__ == '__main__':
s = Solution()
assert s.lengthOfLongestSubstringKDistinct("eceba", 2) == 3
assert s.lengthOfLongestSubstringKDistinct("aa", 1) == 2
assert s.lengthOfLongestSubstringKDistinct("aabbcc", 2) == 4
assert s.lengthOfLongestSubstringKDistinct("abc", 0) == 0
print("All tests passed.")Longest Substring Without Repeating Characters ▼ expand
class Solution:
"""
## 3. Longest Substring Without Repeating Characters
Given a string `s`, find the length of the longest substring without repeating
characters.
### Examples
```text
Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeating characters.
Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest substring.
Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest substring.
```
### Constraints
- `0 <= s.length <= 5 * 10^4`
- `s` consists of English letters, digits, symbols, and spaces.
"""
def lengthOfLongestSubstring_brute(self, s: str) -> int:
# Try all substrings; check uniqueness via set — O(n^3)
# O(n^3) time, O(min(n, m)) space where m is charset size
best = 0
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
if len(set(s[i:j])) == j - i:
best = max(best, j - i)
return best
def lengthOfLongestSubstring(self, s: str) -> int:
# Slide right pointer; if char already in window, jump left past its last occurrence
# char_idx stores the most recent index of each character
# O(n) time, O(min(n, m)) space
char_idx: dict[str, int] = {}
left = best = 0
for right, ch in enumerate(s):
if ch in char_idx and char_idx[ch] >= left:
left = char_idx[ch] + 1
char_idx[ch] = right
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
sol = Solution()
assert sol.lengthOfLongestSubstring("abcabcbb") == 3
assert sol.lengthOfLongestSubstring("bbbbb") == 1
assert sol.lengthOfLongestSubstring("pwwkew") == 3
assert sol.lengthOfLongestSubstring("") == 0
assert sol.lengthOfLongestSubstring_brute("abcabcbb") == 3
assert sol.lengthOfLongestSubstring_brute("bbbbb") == 1
print("All tests passed.")Max Consecutive Ones Iii ▼ expand
"""
LC 1004 - Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of
consecutive 1s in the array if you can flip at most k 0s.
Examples:
```text
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
```
Constraints:
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1
- 0 <= k <= nums.length
"""
from typing import List
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
# Sliding window: expand right always, shrink left when zeros > k
left = 0
zeros = 0
result = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
# Window has more than k zeros — shrink from left
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
result = max(result, right - left + 1)
return result
if __name__ == '__main__':
s = Solution()
assert s.longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2) == 6
assert s.longestOnes([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3) == 10
assert s.longestOnes([1,1,1], 0) == 3
assert s.longestOnes([0,0,0], 0) == 0
print("All tests passed.")Maximum Points You Can Obtain From Cards ▼ expand
"""
LC 1423 - Maximum Points You Can Obtain from Cards
There are several cards arranged in a row. In each step you may take one
card from the beginning or end of the row. You take exactly k cards.
Return the maximum score you can obtain.
Examples:
```text
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Input: cardPoints = [2,2,2], k = 2
Output: 4
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
```
Constraints:
- 1 <= cardPoints.length <= 10^5
- 1 <= cardPoints[i] <= 10^4
- 1 <= k <= cardPoints.length
"""
from typing import List
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
# Approach 1: minimize the sum of the middle window of size n-k
# Taking k from edges = leaving n-k in the middle
n = len(cardPoints)
window = n - k
if window == 0:
return sum(cardPoints)
# Compute sum of first window
curr = sum(cardPoints[:window])
min_mid = curr
for i in range(window, n):
curr += cardPoints[i] - cardPoints[i - window]
min_mid = min(min_mid, curr)
return sum(cardPoints) - min_mid
def maxScore_prefix(self, cardPoints: List[int], k: int) -> int:
# Approach 2: prefix sum from both ends — try all splits of k cards
# take i from front, k-i from back
total = sum(cardPoints)
n = len(cardPoints)
prefix = [0] * (k + 1)
suffix = [0] * (k + 1)
for i in range(1, k + 1):
prefix[i] = prefix[i - 1] + cardPoints[i - 1]
suffix[i] = suffix[i - 1] + cardPoints[n - i]
return max(prefix[i] + suffix[k - i] for i in range(k + 1))
if __name__ == '__main__':
s = Solution()
assert s.maxScore([1,2,3,4,5,6,1], 3) == 12
assert s.maxScore([2,2,2], 2) == 4
assert s.maxScore([9,7,7,9,7,7,9], 7) == 55
assert s.maxScore_prefix([1,2,3,4,5,6,1], 3) == 12
assert s.maxScore_prefix([2,2,2], 2) == 4
print("All tests passed.")Minimum Size Subarray Sum ▼ expand
from typing import List
class Solution:
"""
## 209. Minimum Size Subarray Sum
Given an array of positive integers `nums` and a positive integer `target`, return
the minimal length of a subarray whose sum is greater than or equal to `target`.
If there is no such subarray, return `0` instead.
### Examples
```text
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: [4, 3] has the minimal length under the problem constraint.
Input: target = 4, nums = [1, 4, 4]
Output: 1
Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
```
### Constraints
- `1 <= target <= 10^9`
- `1 <= nums.length <= 10^5`
- `1 <= nums[i] <= 10^4`
"""
def minSubArrayLen_brute(self, target: int, nums: List[int]) -> int:
# Expand from each start until sum >= target — O(n^2)
# O(n^2) time, O(1) space
best = float("inf")
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total += nums[j]
if total >= target:
best = min(best, j - i + 1)
break
return 0 if best == float("inf") else best
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# Expand right to grow sum; shrink left while sum still >= target
# Each element is added and removed at most once — O(n) total
# O(n) time, O(1) space
left = total = 0
best = float("inf")
for right, num in enumerate(nums):
total += num
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else best
if __name__ == "__main__":
sol = Solution()
assert sol.minSubArrayLen(7, [2, 3, 1, 2, 4, 3]) == 2
assert sol.minSubArrayLen(4, [1, 4, 4]) == 1
assert sol.minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 0
assert sol.minSubArrayLen_brute(7, [2, 3, 1, 2, 4, 3]) == 2
assert sol.minSubArrayLen_brute(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 0
print("All tests passed.")Minimum Window Subsequence ▼ expand
"""
LC 727 - Minimum Window Subsequence
Given strings s1 and s2, return the minimum window in s1 such that s2 is
a subsequence of that window. If no such window exists, return "".
Examples:
```text
Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""
```
Constraints:
- 1 <= s1.length <= 2 * 10^4
- 1 <= s2.length <= 100
- s1 and s2 consist of lowercase English letters
"""
class Solution:
def minWindow(self, s1: str, s2: str) -> str:
# Approach 1: two-pointer forward + backward
# Forward: find a window where s2 is a subsequence
# Backward: shrink from right to minimize the window
n, m = len(s1), len(s2)
result = ""
i = 0 # pointer into s1
while i < n:
# Forward pass: match s2 left-to-right starting from i
j = 0
while i < n and j < m:
if s1[i] == s2[j]:
j += 1
i += 1
if j < m:
break # s2 not found, no more windows possible
# i is now one past the end of the window; back up
end = i - 1
# Backward pass: shrink from end to find tightest window
j = m - 1
k = end
while k >= 0 and j >= 0:
if s1[k] == s2[j]:
j -= 1
k -= 1
start = k + 1 # tightest window start
if not result or end - start + 1 < len(result):
result = s1[start:end + 1]
# Restart search from start + 1 to find next candidate
i = start + 1
return result
def minWindow_dp(self, s1: str, s2: str) -> str:
# Approach 2: DP
# dp[i][j] = start index in s1 such that s1[dp[i][j]..i] contains s2[0..j-1]
n, m = len(s1), len(s2)
# dp[j] = earliest start in s1 to match s2[:j] ending at current s1 position
dp = [-1] * (m + 1)
dp[0] = 0 # empty s2 matched at any position
result = ""
for i in range(n):
# Traverse s2 backwards to avoid using updated values
for j in range(min(i + 1, m), 0, -1):
if s1[i] == s2[j - 1] and dp[j - 1] != -1:
dp[j] = dp[j - 1]
# Reset dp[0] for next character
dp[0] = i + 1
if dp[m] != -1:
window = s1[dp[m]:i + 1]
if not result or len(window) < len(result):
result = window
return result
if __name__ == '__main__':
s = Solution()
assert s.minWindow("abcdebdde", "bde") == "bcde"
assert s.minWindow("jmeqksfrsdcmsiwvaovztaqenprpvnbstl", "u") == ""
assert s.minWindow("abcde", "ace") == "abcde"
assert s.minWindow_dp("abcdebdde", "bde") == "bcde"
assert s.minWindow_dp("jmeqksfrsdcmsiwvaovztaqenprpvnbstl", "u") == ""
print("All tests passed.")Minimum Window Substring ▼ expand
from collections import Counter
class Solution:
"""
## 76. Minimum Window Substring
Given two strings `s` and `t` of lengths `m` and `n` respectively, return the
minimum window substring of `s` such that every character in `t` (including
duplicates) is included in the window. If there is no such substring, return the
empty string `""`.
### Examples
```text
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "a"
Output: "a"
Input: s = "a", t = "aa"
Output: ""
```
### Constraints
- `1 <= m, n <= 10^5`
- `s` and `t` consist of uppercase and lowercase English letters.
"""
def minWindow_brute(self, s: str, t: str) -> str:
# Try all substrings starting at i; stop as soon as t is covered — O(n^2*m)
# O(n^2 * m) time, O(m) space
need = Counter(t)
best = ""
for i in range(len(s)):
have: dict[str, int] = {}
for j in range(i, len(s)):
have[s[j]] = have.get(s[j], 0) + 1
if all(have.get(c, 0) >= need[c] for c in need):
if not best or j - i + 1 < len(best):
best = s[i:j + 1]
break
return best
def minWindow(self, s: str, t: str) -> str:
# 'formed' counts how many unique chars in t are satisfied in current window
# Expand right until all chars satisfied; then shrink left to minimize window
# Track best window length and start index throughout
# O(n + m) time, O(m) space
if not t:
return ""
need = Counter(t)
have: dict[str, int] = {}
formed = 0
required = len(need)
left = 0
best_len, best_l = float("inf"), 0
for right, ch in enumerate(s):
have[ch] = have.get(ch, 0) + 1
if ch in need and have[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best_len:
best_len, best_l = right - left + 1, left
lch = s[left]
have[lch] -= 1
if lch in need and have[lch] < need[lch]:
formed -= 1
left += 1
return "" if best_len == float("inf") else s[best_l:best_l + best_len]
if __name__ == "__main__":
sol = Solution()
assert sol.minWindow("ADOBECODEBANC", "ABC") == "BANC"
assert sol.minWindow("a", "a") == "a"
assert sol.minWindow("a", "aa") == ""
assert sol.minWindow_brute("ADOBECODEBANC", "ABC") == "BANC"
assert sol.minWindow_brute("a", "a") == "a"
assert sol.minWindow_brute("a", "aa") == ""
print("All tests passed.")Number Of Substrings Containing All Three Characters ▼ expand
"""
LC 1358 - Number of Substrings Containing All Three Characters
Given a string s consisting only of characters 'a', 'b', and 'c', return
the number of substrings containing at least one occurrence of all three.
Examples:
```text
Input: s = "abcabc"
Output: 10
Input: s = "aaacb"
Output: 3
Input: s = "abc"
Output: 1
```
Constraints:
- 3 <= s.length <= 5 * 10^4
- s consists only of 'a', 'b', 'c'
"""
class Solution:
def numberOfSubstrings(self, s: str) -> int:
# Sliding window: for each right, find smallest left where all 3 present
# Every extension of that window to the left also forms a valid substring
# so add (left + 1) to result
count = {'a': 0, 'b': 0, 'c': 0}
left = 0
result = 0
for right in range(len(s)):
count[s[right]] += 1
# Shrink from left while all 3 chars are present
while count['a'] > 0 and count['b'] > 0 and count['c'] > 0:
count[s[left]] -= 1
left += 1
# left is now one past the smallest valid window end
# so there are `left` valid starting positions for this right
result += left
return result
if __name__ == '__main__':
s = Solution()
assert s.numberOfSubstrings("abcabc") == 10
assert s.numberOfSubstrings("aaacb") == 3
assert s.numberOfSubstrings("abc") == 1
print("All tests passed.")Permutation In String ▼ expand
class Solution:
"""
## 567. Permutation in String
Given two strings `s1` and `s2`, return `true` if `s2` contains a permutation of
`s1`, or `false` otherwise.
In other words, return `true` if one of `s1`'s permutations is a substring of `s2`.
### Examples
```text
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba", a permutation of s1.
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
```
### Constraints
- `1 <= s1.length, s2.length <= 10^4`
- `s1` and `s2` consist of lowercase English letters.
"""
def checkInclusion_brute(self, s1: str, s2: str) -> bool:
# Sort each window of length len(s1) and compare to sorted s1 — O(n*m log m)
# O(n * m log m) time, O(m) space
target = sorted(s1)
m = len(s1)
for i in range(len(s2) - m + 1):
if sorted(s2[i:i + m]) == target:
return True
return False
def checkInclusion(self, s1: str, s2: str) -> bool:
# Fixed-size window of length len(s1); use 26-element frequency arrays
# Slide window right: add new char, remove char that fell out of window
# If frequency arrays match, current window is a permutation of s1
# O(n) time, O(1) space (fixed 26-char alphabet)
if len(s1) > len(s2):
return False
need = [0] * 26
have = [0] * 26
for ch in s1:
need[ord(ch) - ord('a')] += 1
m = len(s1)
for i, ch in enumerate(s2):
have[ord(ch) - ord('a')] += 1
if i >= m:
have[ord(s2[i - m]) - ord('a')] -= 1
if have == need:
return True
return False
if __name__ == "__main__":
sol = Solution()
assert sol.checkInclusion("ab", "eidbaooo") == True
assert sol.checkInclusion("ab", "eidboaoo") == False
assert sol.checkInclusion("a", "a") == True
assert sol.checkInclusion_brute("ab", "eidbaooo") == True
assert sol.checkInclusion_brute("ab", "eidboaoo") == False
print("All tests passed.")Sliding Window Maximum ▼ expand
from typing import List
from collections import deque
class Solution:
"""
## 239. Sliding Window Maximum
You are given an array of integers `nums`, there is a sliding window of size `k`
which is moving from the very left of the array to the very right. You can only see
the `k` numbers in the window. Each time the sliding window moves right by one
position.
Return the max sliding window — an array of the maximum values in each window
position.
### Examples
```text
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Input: nums = [1], k = 1
Output: [1]
```
### Constraints
- `1 <= nums.length <= 10^5`
- `-10^4 <= nums[i] <= 10^4`
- `1 <= k <= nums.length`
"""
def maxSlidingWindow_brute(self, nums: List[int], k: int) -> List[int]:
# For each window position, compute max with built-in — O(n*k)
# O(n * k) time, O(1) extra space
return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# Monotonic deque: front always holds index of current window's max
# Pop from back any index whose value <= current (they can never be max)
# Pop from front if that index has slid out of the current window
# O(n) time, O(k) space
dq: deque[int] = deque() # stores indices, decreasing by value
result: List[int] = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if dq[0] < i - k + 1:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
if __name__ == "__main__":
sol = Solution()
assert sol.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert sol.maxSlidingWindow([1], 1) == [1]
assert sol.maxSlidingWindow([1, -1], 1) == [1, -1]
assert sol.maxSlidingWindow_brute([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert sol.maxSlidingWindow_brute([1], 1) == [1]
print("All tests passed.")Subarrays With K Different Integers ▼ expand
"""
LC 992 - Subarrays with K Different Integers
Given an integer array nums and an integer k, return the number of
good subarrays. A good subarray has exactly k different integers.
Examples:
```text
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Input: nums = [1,2,1,3,4], k = 3
Output: 3
```
Constraints:
- 1 <= nums.length <= 2 * 10^4
- 1 <= nums[i] <= nums.length
- 1 <= k <= nums.length
"""
from typing import List
from collections import defaultdict
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
# exactly(k) = atMost(k) - atMost(k-1)
# Each atMost is a standard sliding window counting subarrays
def atMost(limit: int) -> int:
count = defaultdict(int)
left = res = 0
for right in range(len(nums)):
count[nums[right]] += 1
# shrink until distinct count <= limit
while len(count) > limit:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
# all subarrays ending at right with at most `limit` distinct
res += right - left + 1
return res
return atMost(k) - atMost(k - 1)
if __name__ == '__main__':
s = Solution()
assert s.subarraysWithKDistinct([1,2,1,2,3], 2) == 7
assert s.subarraysWithKDistinct([1,2,1,3,4], 3) == 3
assert s.subarraysWithKDistinct([1,1,1,1], 1) == 10
print("All tests passed.")Sliding Window
Avoid nested loops by maintaining a dynamic window
2
L
0
1
1
5
2
1
3
3
4
2
5
Press "Next Step" to start. Finding minimum subarray with sum ≥ target.