The longest run of ones, with k flips

You are given a list of 0s and 1s and a number k. You may turn at most k of the zeros into ones. What is the longest run of consecutive ones you can end up with?

Worked example#

For [1, 1, 0, 0, 1, 1, 1, 0, 1] with k = 2:

Turn the two zeros at positions 2 and 3 into ones and everything from position 0 to position 6 becomes a run of ones. That is 7, and no choice of two zeros does better.

Saying it plainly#

You never have to decide which zeros to flip. A run you can create is exactly a stretch of the list containing at most k zeros, because those are the ones you would flip. So the question is:

What is the longest stretch containing at most k zeros?

That reads as a window problem, and the flipping disappears from the code entirely.

The idea#

Grow a window on the right. Count the zeros inside it. While that count is above k, move the left edge in, decreasing the count as zeros leave. After each step the window is legal, so its length is a candidate answer.

There is nothing to store but a single counter, because the only thing that makes a window illegal is holding too many zeros.

Note what the window never does: it never shrinks below the best length found so far by more than it has to. Both edges only move right, so every position is visited twice at most and the whole thing is one pass.

The variable window pattern#

Nearly every "longest stretch such that ..." question has this shape:

1. Move the right edge out and update whatever you are tracking.
2. While the window breaks the rule, move the left edge in and undo.
3. Record the length.

What changes between problems is only what you track and what "breaks the rule" means. Here it is a count of zeros against k. In longest substring without repeating characters it is a seen set. In fruit into baskets it is the number of distinct kinds.

Constraints#

• 1 <= n <= 100000
• 0 <= k <= n
• Every value is 0 or 1