Longest Valid Window

In a fixed window the size is given. Here it isn't: the question is "what is the longest contiguous stretch that obeys a rule?" The rule might be "no repeated characters", "at most k zeros" or "at most two distinct values". The window grows as far as it can and shrinks only as much as it must, so every element enters and leaves at most once.

The idea#

Picture the window as a caterpillar crawling along the array.

The head (end) always moves forward to eat the next item. It wants the window as big as possible.
The tail (start) moves only when the window breaks the rule. It moves forward only as far as it must to make the window valid again.

So each loop step has two phases:

Expand (greedy): add nums[end] and assume it is fine.
Contract (correction): while the window is invalid, remove nums[start] and move start right. Once the loop exits, the window is valid, so record end - start + 1.

Why is it safe to drop the start? Adding an element can only make the window "more invalid", and removing one can only help. So when a window breaks the rule, no longer window with the same start can fix it. You can drop the start and move on.

It's also fast, $O(n)$ , because you never reset to the beginning. If 0..5 was valid and index 6 breaks it, you do not re-check 1..6, 2..6 from scratch. You slide the tail until the state works out again. start and end each move at most n times.

How to spot it#

The question usually tells you directly. Look for these signals:

"Longest / maximum length substring or subarray such that ...".
The rule is about the contents of the window: at most k distinct, at most k zeros, no repeats.
Adding an element can only hurt and removing one can only help. This monotonic behavior is what makes shrinking from the left correct.
Constraints around $10^5$ rule out the $O(n^2)$ "try every start" approach.

Template#

The shape is the same for every problem in this family. Only two things change: the window state and the while condition.

state = empty            # sum, count, set or map
start = 0
best = 0
for end in range(len(items)):
    add items[end] to state          # expand: the head always eats
    while state breaks the rule:     # contract: drag the tail
        remove items[start] from state
        start += 1
    record best = max(best, end - start + 1)   # valid here
return best

Most of your thinking goes into the while condition. Ask what state you need (sum, count, map) and which cases make the window invalid. Then combine those cases into the one condition the contraction loop checks.

When the state is a count map, delete a key once its count hits zero. Otherwise the number of keys no longer matches the number of distinct values in the window.

The non-shrinking window#

There is one shortcut you'll see in other people's solutions. For "longest" problems you can replace the while with an if. The window then never shrinks: when it is invalid, it slides right by one and keeps its size. Its size grows only when a longer valid window appears, so the final answer is still correct. Use this on purpose, never by accident.

Pitfalls#

Most wrong answers in this family come from one of these mistakes.

Losing the tail's history. A tempting idea is to store each value's last index and, when the rule breaks, delete the value at start. The value to drop is the one whose last index is smallest, not the one at start. A count map avoids the problem: shrink one item at a time and delete a key only when its count hits zero.
Recording before the window is valid. Update the answer after the while loop, not inside it. (Recording inside the loop is the minimum window pattern.)
The deleted element counts. When the problem deletes an element from the window, the answer is end - start, not end - start + 1.
Shrinking breaks with negatives. If removing an element can make a sum bigger (negative numbers), the window is no longer monotonic. Use prefix sums instead (see Prefix Sum + Hashmap).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Longest Substring Without Repeating Characters

The window state is a set of characters. Shrink while s[end] is already in the set. Here you shrink before you add the new character.

Hint: Fruit Into Baskets

This is "at most k distinct values" with k = 2. The window state is a value-to-count map. Shrink while it holds more than two keys. Delete a key only when its count hits zero.

Hint: Max Consecutive Ones III

The window state is one number: the count of zeros inside the window. Shrink while zeros > k.

Hint: Longest Substring with At Most K Distinct Characters

The window state is a value-to-count map. Shrink while len(count) > k. With k = 2 this is the same problem as Fruit Into Baskets.

Hint: Longest Subarray of 1's After Deleting One Element

Count the zeros in the window and shrink while zeros > 1. The one zero left is the element you delete. So the answer is end - start, not end - start + 1.

Hint: Frequency of the Most Frequent Element

Sort first, and keep the window sum as the state. Pretend every element in the window is raised to nums[end]. That costs nums[end] * size - window_sum. Shrink while nums[end] * size > window_sum + k.

Hint: Longest Substring with At Least K Repeating Characters

There is no natural shrink rule: adding a character can make the window better or worse. Look at the constraints instead: there are only 26 lowercase letters. Run the window once for each target count of distinct characters t = 1..26, and shrink while there are more than t distinct. The window qualifies when the number of characters at frequency k equals t.

Hint: Longest Repeating Character Replacement

A window is valid when length - max_count <= k, where max_count is the count of its most frequent letter. Grow right and shrink left while it is invalid. You never need to lower max_count as you shrink, because only a bigger count can give a longer answer.

Key takeaways#

The head always expands; the tail moves only while the window is invalid.
The hard part is the while condition: list the invalid cases and merge them into one check.
Record the answer after the while loop, once the window is valid again.
Neither pointer moves backwards, so the scan is $O(n)$ .
No natural shrink rule? Look at the constraints for something small to enumerate.

Core idea#

Find the longest contiguous stretch that obeys a rule. Grow the window greedily, and shrink it with a while loop only when the rule breaks.

Key points#

The head (end) always moves forward and adds nums[end].
The tail (start) moves only while the window is invalid.
Record end - start + 1 after the while loop, when the window is valid again.
Neither pointer moves backwards, so the scan is $O(n)$ .
The hard part is the while condition. Decide the state (sum, count, map), list the invalid cases, and merge them into one check.
Spot it: "longest substring or subarray such that ...", a rule about window contents, and constraints near $10^5$ .
Shrinking from the left works only when adding can only hurt and removing can only help.

Common variants#

Only the state and the while condition change.

Problem	Window state	Shrink while
No repeats	set of chars	`s[end]` in set (shrink before adding)
Max consecutive ones III	zero count	`zeros > k`
At most k distinct	value to count map	`len(count) > k`
1s after deleting one	zero count	`zeros > 1`; answer is `end - start`
Most frequent element	window sum, array sorted	`nums[end] * size > window_sum + k`

Template#

state = empty            # sum, count, set or map
start = best = 0
for end in range(len(items)):
    add items[end] to state          # expand
    while state breaks the rule:     # invalid: move the tail
        remove items[start] from state
        start += 1
    best = max(best, end - start + 1)
return best

Pitfalls#

Recording inside the while loop. That is the minimum-window pattern, not this one.
Deleting the value at start from a last-index map. The value to drop has the smallest last index. Use a count map and delete a key only when its count hits zero.
Negative numbers break monotonic shrinking. Use prefix sums instead.
No natural shrink rule (at least k repeating characters)? Look at the constraints. Run the window once for each distinct-count target t = 1..26.

Say it in an interview#

"The head always expands. The tail moves only while the window breaks the rule."
"Each pointer moves at most n times, so this is O(n)."
"For longest problems, an if instead of while also works. The window then slides without shrinking."