LeetCode 3399 - Smallest Substring With Identical Characters II

Difficulty: 🔴 Hard
Topics: String, Binary Search

Solution

Problem Understanding

We are given a binary string s consisting only of '0' and '1', along with an integer numOps. In one operation, we may choose any index and flip the bit at that position. A '0' becomes '1', and a '1' becomes '0'.

Our goal is not to minimize the total number of changes or produce a particular target string. Instead, we want to minimize the length of the longest contiguous substring containing identical characters.

For example, in the string "000001", the longest identical-character substring is "00000" with length 5. By flipping one character, we can break this large block into smaller pieces and reduce the maximum run length.

The problem asks for the minimum possible value of:

the maximum length among all contiguous runs of equal characters,

after performing at most numOps flips.

The constraints are large:

n can be up to 100000
We must handle strings efficiently
Quadratic or exponential approaches are impossible

This immediately suggests that we need something close to O(n log n) or better.

Several edge cases are important:

If numOps = 0, we must simply return the longest existing run.
If the string is already alternating, the answer is 1.
If we are allowed enough flips, we may be able to transform the string into a perfectly alternating pattern.
Large consecutive runs such as "000000000" are the critical structures we must break efficiently.
Since the answer ranges from 1 to n, binary search on the answer is a natural possibility. We are given a binary string s and an integer numOps. Each operation allows us to flip a single character in the string, changing '0' to '1' or '1' to '0'. We may perform at most numOps flips.

The goal is not to minimize the total number of identical substrings, but specifically to minimize the length of the longest contiguous substring consisting entirely of the same character.

For example, if the string is:

then the longest identical-character substring is "00000" with length 5. By flipping one carefully chosen character, we can split this long run into smaller runs.

The output should be the smallest possible value of:

maximum length among all contiguous equal-character runs

after performing at most numOps flips.

The constraints are important:

n can be as large as 100000
A brute-force search over all possible flip combinations is impossible
We need an algorithm close to O(n log n) or better

Because the string contains only '0' and '1', the structure of runs becomes extremely important. Consecutive identical characters form segments, and flips can break large segments into smaller ones.

Several edge cases are important:

Strings already alternating like "010101" already have answer 1
Strings containing one large run like "0000000" require careful splitting
numOps = 0 means we cannot modify anything
Very large numOps may allow a perfectly alternating string
Single-character strings always have answer 1

The key challenge is determining whether a target maximum run length is achievable within the allowed number of flips.

Approaches

Brute Force Approach

A brute force solution would attempt every possible set of flips up to numOps, generate the resulting strings, and compute the longest equal-character substring for each.

This guarantees correctness because it explores every reachable configuration. However, it is completely impractical.

For a string of length n, there are:

$$\sum_{k=0}^{numOps} \binom{n}{k}$$

possible flip combinations. Even for moderate values of n, this becomes astronomically large.

For each generated string, we would also need O(n) time to compute the longest run.

This approach is exponential and cannot handle n = 100000.

Optimal Approach

The key insight is that the answer itself is monotonic.

Suppose we ask:

Can we make every identical-character run have length at most L using at most numOps flips?

If the answer is yes for some L, then it is also yes for every larger value.

This monotonic property allows binary search on the answer.

The remaining challenge is efficiently checking whether a given limit L is feasible.

For a run of length k, we need enough flips to ensure no consecutive block exceeds L.

For example:

Run length 7
Maximum allowed block length 2

We can break the run by flipping every (L + 1)-th character.

The minimum flips needed for a run of length k is:

$$\left\lfloor \frac{k}{L+1} \right\rfloor$$

Why?

Because each flip can split one oversized segment into smaller pieces.

There is one special case:

L = 1

In this situation, the final string must be perfectly alternating. We cannot independently process runs anymore because neighboring runs interact. Instead, we compare against the two possible alternating patterns: A brute-force solution would try every possible combination of flips up to numOps, generate the resulting strings, compute the maximum run length for each, and take the minimum.

This approach is correct because it explores the entire search space. However, it is computationally infeasible.

For a string of length n, there are:

C(n,0) + C(n,1) + ... + C(n,numOps)

possible flip combinations.

Even for moderate values like n = 50, this becomes astronomically large. Since the actual constraint is 100000, brute force is completely impossible.

Key Insight

Instead of directly searching for the optimal final string, we can binary search the answer.

Suppose we ask:

Can we make every identical-character run have length at most k using at most numOps flips?

If the answer is yes for some k, then it will also be yes for every larger value.

This creates a monotonic property:

feasible(k) => feasible(k+1)

That means binary search applies naturally.

The remaining challenge is implementing the feasibility check efficiently.

For a run of length L, we need to determine how many flips are required so that no resulting sub-run exceeds length k.

The optimal strategy is to place flips periodically inside the run.

If we split a run every (k + 1) characters, then each flip reduces the maximum segment size.

For a run of length L, the required number of flips is:

L // (k + 1)

Summing this across all runs gives the minimum flips needed for that k.

There is one special case:

When k = 1, the final string must alternate perfectly
We must explicitly check both alternating patterns:
"010101..."
"101010..."

and compute the minimum flips required.

Thus the solution becomes:

Binary search on answer L
Check feasibility in O(n)
Return the smallest feasible L because the generic formula does not correctly model adjacency interactions for this case.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all flip combinations
Optimal	O(n log n)	O(1)	Binary search with greedy feasibility check

Algorithm Walkthrough

Step 1: Observe the Search Space

The answer must lie between:

1, the smallest possible maximum run length
n, the entire string length

This gives us a natural binary search range.

Step 2: Define the Feasibility Function

We create a function:

can(limit)

which returns whether it is possible to ensure every equal-character substring has length at most limit using at most numOps flips.

Step 3: Handle the Special Case `limit = 1`

If the maximum allowed run length is 1, the final string must alternate.

There are only two alternating possibilities:

"010101..."
"101010..."

We count mismatches with both patterns.

For example:

s = "0000"

pattern1 = "0101" -> 2 mismatches
pattern2 = "1010" -> 2 mismatches

Minimum flips needed is 2.

If the minimum mismatch count is at most numOps, then limit = 1 is feasible.

Step 4: Process Runs for `limit > 1`

Now runs become independent.

Suppose we have a run:

"0000000"

with length 7.

If limit = 2, no segment may exceed length 2.

We can greedily flip every third character:

00 0 00 0 0

The number of required flips is:

$$\left\lfloor \frac{7}{3} \right\rfloor = 2$$

In general, for run length k:

$$\text{flips} = \left\lfloor \frac{k}{limit+1} \right\rfloor$$

We sum this over all runs.

If the total flips needed is at most numOps, then the limit is feasible.

Step 5: Binary Search

We binary search the smallest feasible limit.

For each midpoint:

If feasible, try smaller
Otherwise, try larger

Eventually, the search converges to the minimum answer.

Why it works

The feasibility condition is monotonic.

If we can achieve maximum run length L, then any larger limit is also achievable because it imposes weaker constraints.

The greedy formula for each run is optimal because every flip can break at most one oversized block. Splitting runs at intervals of (L + 1) minimizes the number of required flips.

Therefore, binary search combined with the feasibility check always finds the smallest achievable maximum run length.

Step 1: Observe the monotonic property

If we can achieve maximum run length k, then we can also achieve any larger value.

This means the answer space is ordered and binary searchable.

We binary search over:

1 to n

where n is the string length.

Step 2: Build a feasibility checker

We define:

can(k)

which returns whether we can ensure all runs have length at most k using at most numOps flips.

Step 3: Handle the special case `k = 1`

If the maximum run length must be 1, the final string must alternate.

There are only two possible alternating strings:

010101...
101010...

We count how many positions differ from each pattern.

The minimum mismatch count is the minimum flips required.

If that value is at most numOps, then k = 1 is feasible.

Step 4: Process runs for `k >= 2`

We scan the string and identify contiguous runs.

Example:

000111100

produces runs:

3, 4, 2

For each run length L, we compute:

L // (k + 1)

This is the minimum number of flips needed to ensure no resulting segment exceeds length k.

We accumulate these flips across all runs.

If the total exceeds numOps, then k is impossible.

Step 5: Binary search

We binary search the smallest feasible k.

If can(mid) succeeds:

store the answer
search smaller values

Otherwise:

search larger values

Why it works

The correctness depends on two properties.

First, feasibility is monotonic. If we can reduce all runs to length at most k, then any larger limit is automatically achievable.

Second, for a run of length L, placing flips every (k + 1) positions minimizes the number of required flips. Each flip partitions the run into smaller pieces, and:

L // (k + 1)

is exactly the minimum number of cuts needed so that every resulting segment length is at most k.

Because the feasibility test is optimal and binary search explores the ordered answer space correctly, the algorithm always finds the minimum achievable maximum run length.

Python Solution

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        n = len(s)

        def can(limit: int) -> bool:
            if limit == 1:
                mismatch1 = 0
                mismatch2 = 0
            # Special case: alternating string required
            if limit == 1:
                mismatch1 = 0  # pattern: 010101...
                mismatch2 = 0  # pattern: 101010...

                for i, ch in enumerate(s):
                    expected1 = '0' if i % 2 == 0 else '1'
                    expected2 = '1' if i % 2 == 0 else '0'

                    if ch != expected1:
                        mismatch1 += 1

                    if ch != expected2:
                        mismatch2 += 1

                return min(mismatch1, mismatch2) <= numOps

            operations_needed = 0
            run_length = 1

            for i in range(1, n):
                if s[i] == s[i - 1]:
                    run_length += 1
                else:
                    operations_needed += run_length // (limit + 1)
                    run_length = 1

            operations_needed += run_length // (limit + 1)

            return operations_needed <= numOps

        left = 1
        right = n

        while left < right:
            mid = (left + right) // 2

            if can(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins with the feasibility helper can(limit).

When limit == 1, we compare the string against both alternating patterns. Since any valid string with maximum run length 1 must alternate, this check is exact.

For larger limits, we scan the string and compute consecutive run lengths. Whenever a run ends, we add: left, right = 1, n answer = n

    while left <= right:
        mid = (left + right) // 2

        if can(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer


The implementation follows the exact algorithm described earlier.

The `can()` helper determines whether a target maximum run length is achievable.

The first branch handles `limit == 1`. In this situation, the final string must alternate perfectly, so we compare against both possible alternating patterns and count mismatches.

For larger limits, we scan the string while maintaining the current run length. Whenever the character changes, we finalize the previous run and add:

```python
run_length // (limit + 1)

to the required operations count.

After processing all runs, we compare the total required flips against numOps.

The outer binary search repeatedly tests candidate answers until the smallest feasible limit is found.

The implementation uses only constant extra space and processes each feasibility check in linear time. to the required operation count.

After processing all runs, we compare the total required operations against numOps.

The outer binary search repeatedly tests candidate answers and narrows toward the minimum feasible value.

Go Solution

func minLength(s string, numOps int) int {
	n := len(s)

	can := func(limit int) bool {
		// Special case for alternating strings
		if limit == 1 {
			mismatch1 := 0
			mismatch2 := 0

			for i := 0; i < n; i++ {
				expected1 := byte('0')
				expected2 := byte('1')

				if i%2 == 1 {
					expected1 = '1'
					expected2 = '0'
				}

				if s[i] != expected1 {
					mismatch1++
				}

				if s[i] != expected2 {
					mismatch2++
				}
			}

			if mismatch1 < mismatch2 {
				return mismatch1 <= numOps
			}

			return mismatch2 <= numOps
		}

		operationsNeeded := 0
		runLength := 1

		for i := 1; i < n; i++ {
			if s[i] == s[i-1] {
				runLength++
			} else {
				operationsNeeded += runLength / (limit + 1)
				runLength = 1
			}
		}

		operationsNeeded += runLength / (limit + 1)

		return operationsNeeded <= numOps
	}

	left := 1
	right := n

	for left < right {
		mid := (left + right) / 2

		if can(mid) {
			right = mid
	left, right := 1, n
	answer := n

	for left <= right {
		mid := (left + right) / 2

		if can(mid) {
			answer = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation follows the exact same logic as the Python version.

A closure function can performs the feasibility test. Since Go strings are byte-indexable, we directly compare characters using byte.

Integer division in Go naturally performs floor division, which matches the required formula:

runLength / (limit + 1)

No special overflow handling is needed because all values remain within standard 32-bit integer limits. return answer }


The Go implementation mirrors the Python logic closely.

Since Go strings are byte arrays internally, indexing with `s[i]` directly yields a byte character. No rune conversion is necessary because the input contains only `'0'` and `'1'`.

Integer overflow is not a concern because all values remain within `O(n)` and `n <= 100000`.

The anonymous `can` function captures `s`, `n`, and `numOps` from the outer scope, simplifying the implementation.

## Worked Examples

### Example 1

Input:

s = "000001" numOps = 1


Initial runs:

| Run | Length |
| --- | --- |
| 00000 | 5 |
| 1 | 1 |

Binary search range:

left = 1 right = 6


Check `mid = 3`.

For run length `5`:

$$5 // (3 + 1) = 1$$

Total operations needed:
### Binary Search Iteration 1

| left | right | mid |
| --- | --- | --- |
| 1 | 6 | 3 |

Check `k = 3`.

Runs:

| Run | Length | Required Flips |
| --- | --- | --- |
| 00000 | 5 | 5 // 4 = 1 |
| 1 | 1 | 1 // 4 = 0 |

Total flips needed:


Feasible.

Now search smaller.

Check `mid = 2`.

For run length `5`:

$$5 // (2 + 1) = 1$$

Still feasible.

Check `mid = 1`.

Need alternating string.

Compare:

000001 010101 -> 2 mismatches 101010 -> 4 mismatches


Minimum flips needed is `2`, which exceeds `numOps`.

Therefore answer is:
Search smaller values.

### Binary Search Iteration 2

| left | right | mid |
| --- | --- | --- |
| 1 | 2 | 1 |

Check `k = 1`.

Compare against alternating patterns.

Pattern `"010101"`:

| Position | Actual | Expected | Mismatch |
| --- | --- | --- | --- |
| 0 | 0 | 0 | No |
| 1 | 0 | 1 | Yes |
| 2 | 0 | 0 | No |
| 3 | 0 | 1 | Yes |
| 4 | 0 | 0 | No |
| 5 | 1 | 1 | No |

Total mismatches = 2.

Other pattern also requires more than 1 flip.

Not feasible.

### Binary Search Iteration 3

| left | right | mid |
| --- | --- | --- |
| 2 | 2 | 2 |

Check `k = 2`.

Runs:

| Run | Length | Required Flips |
| --- | --- | --- |
| 00000 | 5 | 5 // 3 = 1 |
| 1 | 1 | 0 |

Total flips = 1.

Feasible.

Final answer:


### Example 2

Input:

s = "0000" numOps = 2


Check `limit = 1`.

Alternating patterns:

0101 -> 2 mismatches 1010 -> 2 mismatches


Minimum required flips:
Check `k = 1`.

Pattern `"0101"`:

| Position | Actual | Expected | Mismatch |
| --- | --- | --- | --- |
| 0 | 0 | 0 | No |
| 1 | 0 | 1 | Yes |
| 2 | 0 | 0 | No |
| 3 | 0 | 1 | Yes |

Total mismatches:


Feasible.

Therefore answer is:
Feasible because `2 <= numOps`.

Answer:


### Example 3

Input:

s = "0101" numOps = 0


Already alternating.

For `limit = 1`:

0101 -> 0 mismatches


Feasible immediately.
The string is already alternating.

`k = 1` requires zero flips.

Answer:


## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Binary search over answer space, each check scans the string once |
| Space | O(1) | Only a few counters and variables are used |

The binary search performs at most `log n` iterations. Each feasibility check scans the string once, producing `O(n)` work per iteration.

Thus the total complexity is:

$$O(n \log n)$$

The algorithm uses constant auxiliary memory because it only tracks counters and run lengths.
| Time | O(n log n) | Binary search performs O(log n) feasibility checks, each scanning the string once |
| Space | O(1) | Only a few counters and variables are used |

The binary search operates over the range `[1, n]`, producing at most `log n` iterations.

Each feasibility check processes the string linearly, either counting mismatches or computing run lengths.

No auxiliary arrays or dynamic data structures are needed, so the extra memory usage remains constant.

## Test Cases

sol = Solution()

assert sol.minLength("000001", 1) == 2 # provided example assert sol.minLength("0000", 2) == 1 # can become alternating assert sol.minLength("0101", 0) == 1 # already alternating

assert sol.minLength("0", 0) == 1 # single character assert sol.minLength("1", 1) == 1 # single character with extra operations

assert sol.minLength("111111", 0) == 6 # no operations allowed assert sol.minLength("111111", 1) == 3 # one split assert sol.minLength("111111", 2) == 2 # more splits possible assert sol.minLength("111111", 3) == 1 # fully alternating possible

assert sol.minLength("101010", 0) == 1 # already optimal assert sol.minLength("100001", 1) == 2 # break central run

assert sol.minLength("00110011", 0) == 2 # multiple equal runs assert sol.minLength("00110011", 2) == 1 # enough operations for alternation

assert sol.minLength("0001000", 1) == 2 # split one large run assert sol.minLength("0001000", 2) == 1 # full alternation achievable

assert sol.minLength("0111110", 1) == 2 # one operation reduces long run assert sol.minLength("0111110", 0) == 5 # unchanged without operations


## Test Summary

| Test | Why |
| --- | --- |
| `"000001", 1` | Provided example with one large run |
| `"0000", 2` | Alternating conversion |
| `"0101", 0` | Already optimal |
| `"0", 0` | Smallest input |
| `"111111", 0` | No modifications allowed |
| `"111111", 3` | Enough flips for full alternation |
| `"100001", 1` | Single long middle run |
| `"00110011", 2` | Multiple independent runs |
| `"0001000", 2` | Symmetric large runs |
| `"0111110", 1` | Large internal run reduction |

## Edge Cases

One important edge case is when the answer becomes `1`. This situation is special because the string must be perfectly alternating. A naive implementation might incorrectly apply the run-based formula even for `limit = 1`, but that does not work because neighboring runs interact after flips. The implementation handles this correctly by explicitly checking the two alternating patterns.

Another critical case occurs when no operations are allowed. In this scenario, the answer is simply the maximum existing run length. Some solutions accidentally assume at least one modification is possible and incorrectly reduce runs. The feasibility function naturally handles this because any required operations greater than zero immediately fail.

Large uniform strings such as `"0000000000"` are also important. These inputs stress whether the run-splitting formula is correct. The implementation uses:

$$\text{runLength} // (limit + 1)$$

which correctly computes the minimum number of flips needed to break oversized runs greedily.

Finally, single-character strings require careful handling because binary search still operates over the range `[1, n]`. The implementation correctly returns `1` immediately since the loop terminates without issue.
assert sol.minLength("000001", 1) == 2  # example 1
assert sol.minLength("0000", 2) == 1  # example 2
assert sol.minLength("0101", 0) == 1  # already alternating

assert sol.minLength("0", 0) == 1  # single character
assert sol.minLength("1", 1) == 1  # single character with extra ops

assert sol.minLength("111111", 0) == 6  # no operations allowed
assert sol.minLength("111111", 1) == 3  # one split
assert sol.minLength("111111", 2) == 2  # more splits
assert sol.minLength("111111", 3) == 1  # fully alternating

assert sol.minLength("010101", 0) == 1  # already optimal
assert sol.minLength("00110011", 0) == 2  # multiple equal runs

assert sol.minLength("0001000", 1) == 3  # one flip insufficient for 2
assert sol.minLength("0001000", 2) == 1  # enough flips for alternating

assert sol.minLength("1010101010", 5) == 1  # extra operations unnecessary

assert sol.minLength("0000000000", 4) == 1  # exactly enough for alternating
assert sol.minLength("0000000000", 3) == 2  # not enough for alternating

assert sol.minLength("011111110", 1) == 3  # large central run
assert sol.minLength("0011111000", 2) == 2  # balancing multiple runs

Test	Why
`"000001", 1`	Verifies sample behavior
`"0000", 2`	Tests achieving full alternation
`"0101", 0`	Already optimal
`"0", 0`	Minimum input size
`"111111", 0`	No modifications allowed
`"111111", 3`	Enough operations for alternating
`"00110011", 0`	Multiple independent runs
`"0001000", 1`	Insufficient operations
`"0001000", 2`	Exact threshold for optimal result
`"1010101010", 5`	Extra operations should not worsen answer
`"0000000000", 4`	Large run split completely
`"011111110", 1`	Central dominant run
`"0011111000", 2`	Several large runs interacting

Edge Cases

Edge Case 1: Already Alternating Strings

Strings like:

010101010

already have maximum run length 1.

A buggy implementation might still attempt unnecessary modifications or incorrectly compute feasibility for k = 1.

The implementation handles this correctly by explicitly checking alternating patterns and computing mismatches. If mismatches are zero, the answer immediately becomes 1.

Edge Case 2: One Extremely Large Run

Consider:

0000000000

This case stresses the formula:

L // (k + 1)

because all optimization depends on splitting one run efficiently.

Incorrect formulas such as:

(L - 1) // k

produce wrong answers for several inputs.

The implementation uses the correct derivation based on periodic splitting positions.

Edge Case 3: No Operations Allowed

When:

numOps = 0

the answer must equal the existing maximum run length.

This is a common source of off-by-one mistakes during feasibility checks.

The implementation naturally handles this because feasibility only succeeds when required operations are zero.

Edge Case 4: Large `numOps`

If enough operations exist, the optimal answer becomes 1.

However, not every string can become alternating with an arbitrary small number of flips.

The explicit alternating-pattern check ensures we compute the exact minimum flips required instead of relying on the generic run formula, which is insufficient for k = 1.

LeetCode 3399 - Smallest Substring With Identical Characters II

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Step 1: Observe the Search Space

Step 2: Define the Feasibility Function

Step 3: Handle the Special Case limit = 1

Step 4: Process Runs for limit > 1

Step 5: Binary Search

Why it works

Step 1: Observe the monotonic property

Step 2: Build a feasibility checker

Step 3: Handle the special case k = 1

Step 4: Process runs for k >= 2

Step 5: Binary search

Why it works

Python Solution

Go Solution

Edge Cases

Edge Case 1: Already Alternating Strings

Edge Case 2: One Extremely Large Run

Edge Case 3: No Operations Allowed

Edge Case 4: Large numOps

Step 3: Handle the Special Case `limit = 1`

Step 4: Process Runs for `limit > 1`

Step 3: Handle the special case `k = 1`

Step 4: Process runs for `k >= 2`

Edge Case 4: Large `numOps`