Problem 360389 · medium · Level 03 Linear Management & Searching

Longest Run with a Flip Budget

sliding window · variable-size window · binary arrays

A conveyor belt scanner reports each package as 1 (passed) or 0 (rejected) in bits. You may override up to k rejections, turning those 0s into 1s. Return the length of the longest run of consecutive 1s you can obtain.

Examples

Input:  bits = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Explanation: override the two zeros at indices 4 and 5 to get [1,1,1,0,1,1,1,1,1,1,0].

Input:  bits = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], k = 3
Output: 10

Constraints

  • 1 <= len(bits) <= 10**5
  • bits[i] is 0 or 1, 0 <= k <= len(bits)
  • Target complexity: O(n) time; trying every start position is too slow for the largest tests.

Goals

  • Maintain the number of zeros inside a variable window
  • Shrink from the left only when the flip budget is exceeded
Starting Python…