0915HardStringBinary Search

Shortest Longest Run After Flips

Tracked in this browser only

Trains the technique from

LeetCode 3399Smallest Substring With Identical Characters II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape reads s, a string of '0' and '1'. Up to numOps characters may be flipped to the other one, chosen freely and independently.

A run is a stretch of equal neighbouring characters. Make the tape's longest run as short as you can, and return that length.

Examples

Example 1

Input: s = "1100011100", numOps = 4
Output: 1

Four flips are enough to leave no run longer than one, since the tape needs four characters changed to alternate throughout.

Example 2

Input: s = "0000000000", numOps = 1
Output: 5

One flip splits the run of ten into pieces, and the best it can do is leave a longest run of five.

Example 3

Input: s = "0000000000", numOps = 0
Output: 10

With no flips allowed the tape keeps its single run of ten.

Constraints

1 <= s.length <= 10^5
s[i] is either '0' or '1'
0 <= numOps <= s.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_length(s: str, numOps: int) -> int:

Java

public int minLength(String s, int numOps)

The intended approach

Time O(n log n) for a tape of length n: each candidate costs one pass over the runs.Space O(1) beyond the input.

Ask instead how many flips are needed to get every run down to some length `m`, since that count only falls as `m` grows, which is what lets the answer be found by halving the range. For `m` of two or more, the runs are independent: a run of length `L` needs a flip every `m + 1` characters to break it into pieces of at most `m`, which is `L` divided by `m + 1`, rounded down, and those flips never interfere between runs because each one sits strictly inside its own run. Adding that over the runs gives the cost. An `m` of one is different, because it demands the whole tape alternate, and only two tapes of a given length do. So its cost is the smaller of the two distances to those, which one pass measures. With both cases in hand, halve the range from one up to the tape's length.

Pythonentry point: min_length

def min_length(s, numOps):
    n = len(s)

    def cost(m):
        if m == 1:
            off = 0
            for i in range(n):
                want = "0" if i % 2 == 0 else "1"
                if s[i] != want:
                    off += 1
            other = n - off
            return off if off < other else other
        total = 0
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            total += (j - i) // (m + 1)
            i = j
        return total

    low = 1
    high = n
    while low < high:
        mid = (low + high) // 2
        if cost(mid) <= numOps:
            high = mid
        else:
            low = mid + 1
    return low

The obvious version

Try every set of positions that could be flipped, keep the ones inside the budget, and for each read off the longest run of the tape it produces, taking the smallest such length. Exponential in the tape length and it makes no argument about how runs break.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_length(s, numOps):
    n = len(s)
    best = n
    for mask in range(1 << n):
        flips = 0
        for i in range(n):
            if mask >> i & 1:
                flips += 1
        if flips > numOps:
            continue
        built = []
        for i in range(n):
            ch = s[i]
            if mask >> i & 1:
                ch = "1" if ch == "0" else "0"
            built.append(ch)
        longest = 1
        run = 1
        for i in range(1, n):
            if built[i] == built[i - 1]:
                run += 1
            else:
                run = 1
            if run > longest:
                longest = run
        if longest < best:
            best = longest
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in