A strip of fairy lights is a list of bulbs: 1 is a working bulb and 0 is a dead one. You have k spare bulbs, so you can fix at most k dead bulbs (turn those 0s into 1s).
Write longest_ones(bits: list[int], k: int) -> int: the length of the longest run of consecutive working bulbs you can end up with.
longest_ones([1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], 2) # 7: fix the bulbs at 4 and 5, then 2..8 all work
longest_ones([1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1], 1) # 5: fix the bulb at 4, then 3..7 all work
longest_ones([0, 0, 1, 0], 0) # 1: no spares, the single working bulb
longest_ones([0, 0, 0], 5) # 3: fix all three, two spares left over
Constraints: 1 <= len(bits) <= 2 * 10^5, every value is 0 or 1, 0 <= k <= len(bits).
⭐ Bonus: trying every start and walking right from it still passes; a speed test with 200,000 bulbs and up to 20,000 spares earns a star in O(n).
Show hint
the question is the same as "the longest stretch that contains at most k zeros". Grow a stretch on the right, and when it holds too many zeros, shrink it from the left.