Variable-Size Windows
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)When the block size is not given, the window has to change its own size. One pointer grows it and the other shrinks it. This pattern solves "longest" and "shortest" questions in one pass.
Grow on the right, shrink on the left
Variable-size window is a window whose two ends move on their own: the right end grows it, and the left end shrinks it whenever a rule is broken. The window length changes as you go.
Sometimes the size is not given. You want the longest block that still follows a rule. Move right to add an item. If the rule breaks, move left until it holds again.
orders = [3, 1, 4, 1, 5, 2]limit = 8left = total = best = 0for right, value in enumerate(orders): total += value while total > limit: total -= orders[left] left += 1 best = max(best, right - left + 1)print(best)The window is orders[left:right + 1], so its length is right - left + 1. This works because every number is positive: removing an item always lowers the total.
Longest substring without repeats
Window invariant is the rule that is true for the window after every step, such as "no letter appears twice". Grow the window, then shrink it until the invariant holds again.
Find the longest piece of text with no letter twice. Keep the letters of the window in a set. If the new letter is already there, shrink from the left until it is gone.
text = "abcabcbb"seen = set()left = best = 0for right, ch in enumerate(text): while ch in seen: seen.remove(text[left]) left += 1 seen.add(ch) best = max(best, right - left + 1)print(best)Example 1 · Brute force: test every substring
text = "abcabcbb"best = 0for i in range(len(text)): for j in range(i + 1, len(text) + 1): part = text[i:j] if len(set(part)) == len(part): best = max(best, len(part))print(best)3
What this code does
- Every start and end is tried, and a set tells whether letters repeat.
- This is O(n^2) pieces, and each check costs more. It is too slow for long text.
Example 2 · Better: watch the window move
text = "abcabcbb"seen = set()left = 0for right, ch in enumerate(text): while ch in seen: seen.remove(text[left]) left += 1 seen.add(ch) print(right, text[left:right + 1])0 a 1 ab 2 abc 3 bca 4 cab 5 abc 6 cb 7 b
What this code does
- The printed piece is the current window after each step.
- At right = 3 the letter a repeats, so a is dropped from the left and the window becomes bca.
After each step the window has no repeated letter. Each letter enters once and leaves at most once, so the loops together do O(n) work even though one is inside the other.
Smallest subarray with a sum
Now the goal is the shortest block with a sum of at least a target. Grow until the sum is big enough. While it is, record the length and drop items from the left.
nums = [2, 3, 1, 2, 4, 3]target = 7left = total = 0best = len(nums) + 1for right, value in enumerate(nums): total += value while total >= target: best = min(best, right - left + 1) total -= nums[left] left += 1print(best if best <= len(nums) else 0)Example 3 · Brute force: smallest subarray with a sum
nums = [2, 3, 1, 2, 4, 3]target = 7best = 0for i in range(len(nums)): total = 0 for j in range(i, len(nums)): total += nums[j] if total >= target: length = j - i + 1 if best == 0 or length < best: best = length breakprint(best)2
What this code does
- Each start grows to the right until the sum reaches the target, then stops.
- The cost is O(n^2) in the worst case.
Example 4 · Optimal: a function with a "no answer" case
def min_length(nums, target): left = total = 0 best = len(nums) + 1 for right, value in enumerate(nums): total += value while total >= target: best = min(best, right - left + 1) total -= nums[left] left += 1 return best if best <= len(nums) else 0
print(min_length([2, 3, 1, 2, 4, 3], 7))print(min_length([1, 1, 1], 10))print(min_length([8], 5))2 0 1
What this code does
- The loop is O(n) time and O(1) space.
- The middle call has no block big enough, so it returns 0.
- A single item can be a window of length 1.
The answer is recorded inside the while, while the window is valid. If no block reaches the target, best stays larger than the list and we print 0.
Jump left with a last-seen dictionary
Instead of removing one letter at a time, remember where each letter was last seen. When a letter repeats, jump left just past its old position.
text = "abba"last = {}left = best = 0for right, ch in enumerate(text): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1)print(best)Example 5 · Longest substring with a last-seen dictionary
def longest_unique(text): last = {} left = best = 0 for right, ch in enumerate(text): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best
print(longest_unique("abba"))print(longest_unique("tmmzuxt"))print(longest_unique(""))2 5 0
What this code does
- The window jumps instead of shrinking one step at a time.
- In "abba" the second a is ignored as a repeat because the first a is already outside the window.
- An empty text gives 0.
Example 6 · Longest streak with at most k outages
days = [1, 1, 0, 1, 1, 0, 0, 1, 1, 1]k = 2left = zeros = best = 0for right, day in enumerate(days): if day == 0: zeros += 1 while zeros > k: if days[left] == 0: zeros -= 1 left += 1 best = max(best, right - left + 1)print(best)7
What this code does
- A 0 is a day the service was down. The window may hold at most k zeros.
- The invariant is
zeros <= k; the left side moves until it is true again.
The check last[ch] >= left ignores an old sighting that is already outside the window. Without it, left could move backwards.
Next step
Check your understanding
11 quick questions