Description
The window changes size to fit the target condition; you grow it until the condition fails, then shrink it till the condition is met again.
?
Reach for when
- Longest subarray/substring that still satisfies a constraint → grow right, shrink left only when it breaks, track max size.
- Shortest subarray/substring that reaches a goal → grow right until valid, then squeeze left, track min size.
Runtime
O(n)
Visualization
Pseudocode
l = 0
r = 0
while r < len(array)
while over extended past the condition:
decrease state by l
l+=1
r+=1
update the state by r
return answer
Code
def longest_window(arr):
state = new_state()
l = 0
best = 0
for r in range(len(arr)):
add(state, arr[r])
while not valid(state):
remove(state, arr[l])
l += 1
best = max(best, r - l + 1)
return best
def shortest_window(arr):
state = new_state()
l = 0
best = float("inf")
for r in range(len(arr)):
add(state, arr[r])
while valid(state):
best = min(best, r - l + 1)
remove(state, arr[l])
l += 1
return best if best != float("inf") else 0