Longest winning streak after erasing k losing days

Question

A desk's daily results are a binary array: 1 for a winning day, 0 for a losing day. You are allowed to erase (flip to a win) at most k losing days. Find the length of the longest run of consecutive wins you can create.

days = [1, 1, 0, 1, 0, 1, 1, 0, 1], k = 2
-> 7           # erase the two 0s among days 3..8 (indices 2 and 4)

Return the maximum achievable streak length. Aim for $O(n)$ .

Accepted Answer

Reframe: a window can be turned into a pure winning streak if and only if it holds at most k zeros, because you spend one erase per zero. So this is the k-distinct window in disguise, with "number of zeros" as the quantity to cap at k. Grow right; whenever the window holds more than k zeros, shrink left until it holds k again. Tracing the example with k = 2: the window 1 1 0 1 0 1 1 (indices 0..6) holds exactly two zeros, length 7. Extending to index 7 (a third zero) forces left forward past the first zero, so no window beats 7. Time O(n), each index enters and leaves once, space O(1). Takeaw…

Longest winning streak after erasing k losing days

Your answer

More Coding questions