Maintain a window over an array or string, expanding right and shrinking left to find the optimal sub-array satisfying a condition.
Problems: 6
Easy: 1
Medium: 3
Hard: 2
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Given array prices where prices[i] is the price on day i, find the maximum profit from one buy and one sell (buy before sell). Return 0 if no profit possible.
Use a dict storing the last seen index of each character. When a repeat is found, jump the left pointer past the previous occurrence.
Python Solution
def lengthOfLongestSubstring(s):
last_seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # shrink window
last_seen[ch] = right
best = max(best, right - left + 1)
return best
Key idea: Sliding window where left is the start of the valid window. When we see a repeated character that's inside the window, jump left past it. Always update the last seen position.
Time: O(n). Space: O(min(n,m)) where m is the alphabet size.
A window is valid if (window_size - max_count_in_window) ≤ k. What's the key invariant about max_count as the window grows?
Python Solution
def characterReplacement(s, k):
count = {}
left = best = max_count = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
max_count = max(max_count, count[ch])
# Characters to replace = window_size - max_count
if (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
Key idea: Replacements needed = window_size - most_frequent_char_count. If replacements > k, shrink from the left. We never need to decrease max_count — if it was valid before, tracking the historical max is fine.
A sliding window of length len(s1) across s2 — if the window's character counts match s1's counts, we found a permutation.
Python Solution
from collections import Counter
def checkInclusion(s1, s2):
if len(s1) > len(s2):
return False
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
right_ch = s2[i]
left_ch = s2[i - len(s1)]
window[right_ch] += 1
window[left_ch] -= 1
if window[left_ch] == 0:
del window[left_ch]
if window == need:
return True
return False
Key idea: Fixed-size sliding window of length len(s1). Slide it across s2, adding the new right character and removing the old left character. Compare Counter objects at each step.
Expand right until you have all required chars. Then shrink from the left as long as the window is still valid. Track the best valid window seen.
Python Solution
from collections import Counter
def minWindow(s, t):
if not t:
return ""
need = Counter(t)
window = {}
formed = 0 # how many chars satisfy their required count
required = len(need) # distinct chars we need
left = 0
best = float('inf'), 0, 0
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
lch = s[left]
window[lch] -= 1
if lch in need and window[lch] < need[lch]:
formed -= 1
left += 1
return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]
Key idea: Two pointers. Expand right until all required characters are satisfied (formed == required). Then shrink left to minimize the window, saving the best. Repeat.
Use a deque that stores indices in decreasing order of their values. The front is always the max. Remove indices that fall outside the window.
Python Solution
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices; nums[dq[0]] is always the window max
result = []
for i, n in enumerate(nums):
# Remove indices outside the window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove indices whose values are smaller than current
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
Key idea: A monotonic deque maintains candidate indices in decreasing value order. The front is the current window max. As we slide right, pop from the back anything smaller than the new element (they can never be a future max).
Time: O(n) — each index pushed/popped once. Space: O(k).