#3399

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Smallest Substring With Identical Characters II

Find the minimal length of a substring with identical characters using binary search and controlled character flips efficiently.

string binary search

Problem Statement

You are given a binary string s of length n and an integer numOps. You may perform at most numOps operations, where each operation flips a single character from '0' to '1' or vice versa. Your goal is to determine the minimal possible length of the longest substring in s where all characters are identical after applying at most numOps operations.

Return this minimal length. The challenge requires efficiently checking all candidate lengths using binary search and verifying feasibility with controlled flips. For example, if s = "000001" and numOps = 1, flipping one character can reduce the maximal identical substring length from 5 to 2.

Examples

Example 1

Input: s = "000001", numOps = 1

Output: 2

By changing s[2] to '1' , s becomes "001001" . The longest substrings with identical characters are s[0..1] and s[3..4] .

Example 2

Input: s = "0000", numOps = 2

Output: 1

By changing s[0] and s[2] to '1' , s becomes "1010" .

Example 3

Input: s = "0101", numOps = 0

Output: 1

Example details omitted.

Constraints

1 <= n == s.length <= 105
s consists only of '0' and '1'.
0 <= numOps <= n

Solution Approach

Binary Search on Substring Length

Treat the answer space as the range of possible maximal substring lengths. Perform binary search on this range. For each candidate length, check if it is possible to achieve it by using at most numOps flips.

Sliding Window Feasibility Check

For a candidate length L, use a sliding window to count the number of flips needed to make all characters identical in each window. If any window requires flips <= numOps, the candidate length is feasible.

Optimize with Prefix Sums

Precompute prefix sums for both '0' and '1' counts. This allows constant-time queries for the number of flips needed in any window, reducing overall complexity from O(n^2) to O(n log n) when combined with binary search.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) because binary search explores O(log n) candidate lengths, and each feasibility check with prefix sums takes O(n). Space complexity is O(n) for storing prefix sums for '0' and '1'.

What Interviewers Usually Probe

Focus on binary search for the answer rather than trying to brute-force substrings.
Consider efficient feasibility checks using prefix sums or sliding windows.
Watch for off-by-one errors in substring window calculations.

Common Pitfalls or Variants

Common pitfalls

Miscounting flips needed in the sliding window, leading to incorrect feasibility results.
Not handling edge cases when numOps = 0 or equal to string length.
Assuming flipping only one character type is enough without checking both '0' and '1' windows.

Follow-up variants

Find minimal longest substring length with at most k character replacements in a multi-character string.
Determine minimal length after exactly numOps flips instead of at most numOps.
Apply the same approach for circular strings where the end connects to the start.

FAQ

What pattern does Smallest Substring With Identical Characters II use?

It uses binary search over the valid answer space, checking feasible substring lengths with sliding windows.

How do I efficiently check if a candidate length is possible?

Use a sliding window or prefix sums to count flips required to unify characters in each substring window.

What should I consider when numOps = 0?

The minimal length is simply the length of the longest existing identical substring without any flips.

Can this method handle very large strings?

Yes, using O(n log n) time with prefix sums and binary search scales to strings up to 10^5 characters.

Why not try brute-force all substrings?

Brute-force is too slow; the problem pattern explicitly favors binary search over substring lengths to meet efficiency constraints.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        def check(m: int) -> bool:
            cnt = 0
            if m == 1:
                t = "01"
                cnt = sum(c == t[i & 1] for i, c in enumerate(s))
                cnt = min(cnt, n - cnt)
            else:
                k = 0
                for i, c in enumerate(s):
                    k += 1
                    if i == len(s) - 1 or c != s[i + 1]:
                        cnt += k // (m + 1)
                        k = 0
            return cnt <= numOps

        n = len(s)
        return bisect_left(range(n), True, lo=1, key=check)

Continue Practicing

#3455 shortest matching substring #3501 maximize active section with trade ii #3292 minimum number of valid strings to form target ii