The sliding-window technique maintains a contiguous range over a sequence, expanding and shrinking it as you scan — turning many O(n²) substring/subarray problems into O(n). The dual of the two-pointer technique for window-shaped subproblems.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n) |
O(n) |
O(1) |
Maintain left and right indices delimiting the current window. Expand right while the window stays valid; when it becomes invalid, shrink from the left until it's valid again. Track the answer as you go. Each index moves forward at most n times — total O(n).
def longest_substring_no_repeat(s):
"""Length of the longest substring with no repeating characters."""
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
def min_subarray_sum(arr, target):
"""Smallest contiguous subarray with sum >= target (positive ints)."""
left = 0
s = 0
best = float("inf")
for right, x in enumerate(arr):
s += x
while s >= target:
best = min(best, right - left + 1)
s -= arr[left]
left += 1
return best if best != float("inf") else 0
print(longest_substring_no_repeat("abcabcbb")) # 3 ('abc')
print(min_subarray_sum([2, 3, 1, 2, 4, 3], 7)) # 2 ([4, 3])