Break Up the Long Runs

Hard

You get a binary string bits and an integer flips. At most flips times you may pick any character and flip it, turning 0 into 1 or vice versa. A run is a stretch of consecutive equal characters. Flip characters so that the longest run in the string is as short as possible, and return its length.

Example 1

bits="000000", flips=2 → 2

Flip positions 2 and 5 to get 001001, whose longest run is 2. Two flips are not enough to get every run down to 1.

Example 2

bits="1110111", flips=1 → 3

One flip can break only one of the two 111 runs; the other stays. The answer is 3.

Example 3

bits="0110", flips=2 → 1

Constraints

1 ≤ len(bits) ≤ 1000
bits consists only of 0 and 1
0 ≤ flips ≤ len(bits)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Enumeration

Similar problems

Where Moss Species Meet Hard Flowerbed Beauty on a Budget Hard Cut a Block to Climb Easy Median Across Two Arrays Hard Minimum of a Shifted Array With Repeats Hard

Input

bits="000000", flips=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 120 tests on the server, hidden ones included.