Watch 6 video solutions for Smallest Substring With Identical Characters II, a hard level problem involving String, Binary Search. 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 <= 105s consists only of '0' and '1'.0 <= numOps <= nProblem Overview: You are given a string and a limited number of modification operations. The goal is to minimize the length of the longest substring consisting of identical characters after applying at most k changes. The result is the smallest possible maximum run length achievable with those operations.
Approach 1: Linear Search on Maximum Run Length (Brute Force) (Time: O(n^2), Space: O(1))
Start by computing runs of identical characters in the string. Try every possible maximum allowed run length L from 1 to n. For each candidate L, iterate through all runs and calculate how many characters must be changed to break that run so no segment exceeds L. A run of length r requires roughly r / (L + 1) modifications because each modification splits the run. If the total required operations stay within k, the value is feasible. This approach is straightforward but too slow for large inputs because it checks every possible length.
Approach 2: Binary Search on the Answer (Greedy Check) (Time: O(n log n), Space: O(1))
The key observation: if a maximum run length L is achievable, then any value larger than L is also achievable. This monotonic property makes the problem ideal for binary search. Search the smallest feasible L in the range [1, n]. For each midpoint, scan the string and group consecutive identical characters. For a run of length r, compute the number of changes required to ensure each segment length is at most L. Each modification effectively breaks the run, so the required operations are r / (L + 1). Accumulate the operations across all runs and stop early if the count exceeds k.
The feasibility check is linear because it processes each character once while tracking run lengths. Combined with binary search, the total complexity becomes O(n log n), which handles large strings comfortably. The algorithm relies on simple iteration and greedy splitting of runs rather than complex data structures.
Recommended for interviews: Binary search on the answer with a greedy feasibility check is the expected solution. The brute-force attempt shows you understand the relationship between run length and required modifications, but the O(n log n) approach demonstrates strong problem-solving skills using monotonic properties and binary search over the answer space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Search on Maximum Run Length | O(n^2) | O(1) | Useful for understanding the relationship between run length and required modifications |
| Binary Search with Greedy Run Splitting | O(n log n) | O(1) | Optimal solution for large inputs; leverages monotonic property of feasible run lengths |