Show problems as
Classic problem #3399HardStringBinary Search

Smallest Substring With Identical Characters II

Real-world version: Shortest Longest Run After Flips
Tracked in this browser only
Read Smallest Substring With Identical Characters II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_length(s: str, numOps: int) -> int:
Java
public int minLength(String s, int numOps)

More on the same topics