Break Up the Long Runs: Long Input

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) ≤ 10⁵
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

String Binary Search

Similar problems

Numbers From Working Keys Hard Longest Repeated Fragment Hard Suffixes Echoing the Start Hard Numbered Text Chunks Hard Cheapest Cut to a Subsequence Hard

Input

bits="000000", flips=2

Expected

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