Longest Lit Streak With Repairs

MediumSliding Window

Problem

A string of festival lights is described by bits, where 1 is a working bulb and 0 a broken one. You have k spare bulbs, so you can fix at most k broken positions.

Return the length of the longest run of consecutive working bulbs you can achieve.

Example 1

Input:
bits = [1, 0, 1, 1, 0, 0, 1], k = 1
Output:
4

Fix position 1 and positions 0..3 are all lit.

Example 2

Input:
bits = [0, 0, 0], k = 0
Output:
0

Constraints

  • 1 ≤ bits.length ≤ 10^5
  • bits[i] is 0 or 1
  • 0 ≤ k ≤ bits.length

Hint

Show the first hint

Rephrase: find the longest window that contains at most k zeros.

Walkthrough

How to approach it

01Clarify before coding

  • Must I use all k repairs? No, at most k.
  • Can k exceed the number of zeros? Yes; then the whole array becomes lit.
  • Is the answer 0 possible? Yes, when there are no 1s and k = 0.

02Brute force

For each start, extend right while the number of zeros stays ≤ k, and keep the longest.

Cost: O(n²) time, around 5·10^9 steps at n = 10^5.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.