Watch 3 video solutions for Smallest Substring With Identical Characters I, a hard level problem involving Array, Binary Search, Enumeration. This walkthrough by Aryan Mittal has 3,824 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a binary string s of length n and an integer numOps.
You are allowed to perform the following operation on s at most numOps times:
i (where 0 <= i < n) and flip s[i]. If s[i] == '1', change s[i] to '0' and vice versa.You need to minimize the length of the longest substring of s such that all the characters in the substring are identical.
Return the minimum length after the operations.
Example 1:
Input: s = "000001", numOps = 1
Output: 2
Explanation:
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
Explanation:
By changing s[0] and s[2] to '1', s becomes "1010".
Example 3:
Input: s = "0101", numOps = 0
Output: 1
Constraints:
1 <= n == s.length <= 1000s consists only of '0' and '1'.0 <= numOps <= nProblem Overview: You’re given a string and a limited number of character modifications. The goal is to minimize the length of the longest substring consisting of identical characters after performing at most k changes. Instead of directly constructing the final string, treat it as an optimization problem: what is the smallest possible maximum run length you can achieve?
Approach 1: Enumerate Possible Maximum Length (Brute Force) (Time: O(n^2), Space: O(1))
Try every possible maximum substring length L from 1 to n. For each candidate length, scan the string and measure contiguous runs of identical characters. If a run has length r, you must break it so no segment exceeds L. That requires floor(r / (L + 1)) character changes because every L+1 characters you need a modification to split the run. Sum the required changes across all runs and check if the total is ≤ k. This works but testing every L makes it too slow for large inputs.
Approach 2: Binary Search on the Answer (Optimal) (Time: O(n log n), Space: O(1))
The key observation: if a maximum run length L is achievable with ≤ k changes, then any value larger than L is also achievable. This monotonic property allows binary search over the answer range [1, n]. For each midpoint L, perform a single pass through the string and compute how many changes are required to break runs longer than L. The run counting step is simple array/enumeration: iterate through the string, track the current run length, and apply floor(run / (L + 1)) to accumulate needed operations. If the total exceeds k, reduce the search range; otherwise try a smaller L.
This approach converts a difficult string modification problem into a decision problem checked in linear time. Binary search reduces the candidate space quickly, while the run-length calculation keeps each check efficient.
Recommended for interviews: Start by describing the brute-force enumeration to show you understand how modifications break character runs. Then move to binary search on the maximum allowed substring length. Interviewers typically expect the O(n log n) solution because it demonstrates recognizing monotonic constraints and combining run-length enumeration with binary search.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate Maximum Length (Brute Force) | O(n^2) | O(1) | Useful for understanding how many modifications are needed to break long runs |
| Binary Search + Run Enumeration | O(n log n) | O(1) | General optimal solution when the answer range is monotonic |