Smallest Substring With Identical Characters I solution and explanation
Google
3 more videos on this problem
3398, 3399. Smallest Substring With Identical Characters I & II | 3398 I | Binary Search | !GreedyAryan Mittal · 26:05 · 3K views
3398. Smallest Substring With Identical Characters I (Leetcode Hard)Programming Live with Larry · 50:17 · 422 views
Leetcode 3398 and 3399 | Smallest Substring With Identical Characters | Weekly Contest 429Road To FAANG · 16:33 · 417 views
Weekly Contest 429 | 3396, 3397, 3398 and 3399 | LeetcodeAmit Choraria · 30:11 · 255 views
The problem
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:
- Select any index
i(where0 <= i < n) and flips[i]. Ifs[i] == '1', changes[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 <= 1000sconsists only of'0'and'1'.0 <= numOps <= n
Approach overview
Problem 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.
Solution
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)class Solution {
private char[] s;
private int numOps;
public int minLength(String s, int numOps) {
this.numOps = numOps;
this.s = s.toCharArray();
int l = 1, r = s.length();
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private boolean check(int m) {
int cnt = 0;
if (m == 1) {
char[] t = {'0', '1'};
for (int i = 0; i < s.length; ++i) {
if (s[i] == t[i & 1]) {
++cnt;
}
}
cnt = Math.min(cnt, s.length - cnt);
} else {
int k = 0;
for (int i = 0; i < s.length; ++i) {
++k;
if (i == s.length - 1 || s[i] != s[i + 1]) {
cnt += k / (m + 1);
k = 0;
}
}
}
return cnt <= numOps;
}
}class Solution {
public:
int minLength(string s, int numOps) {
int n = s.size();
auto check = [&](int m) {
int cnt = 0;
if (m == 1) {
string t = "01";
for (int i = 0; i < n; ++i) {
if (s[i] == t[i & 1]) {
++cnt;
}
}
cnt = min(cnt, n - cnt);
} else {
int k = 0;
for (int i = 0; i < n; ++i) {
++k;
if (i == n - 1 || s[i] != s[i + 1]) {
cnt += k / (m + 1);
k = 0;
}
}
}
return cnt <= numOps;
};
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};function minLength(s: string, numOps: number): number {
const n = s.length;
const check = (m: number): boolean => {
let cnt = 0;
if (m === 1) {
const t = '01';
for (let i = 0; i < n; ++i) {
if (s[i] === t[i & 1]) {
++cnt;
}
}
cnt = Math.min(cnt, n - cnt);
} else {
let k = 0;
for (let i = 0; i < n; ++i) {
++k;
if (i === n - 1 || s[i] !== s[i + 1]) {
cnt += Math.floor(k / (m + 1));
k = 0;
}
}
}
return cnt <= numOps;
};
let [l, r] = [1, n];
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}func minLength(s string, numOps int) int {
check := func(m int) bool {
m++
cnt := 0
if m == 1 {
t := "01"
for i := range s {
if s[i] == t[i&1] {
cnt++
}
}
cnt = min(cnt, len(s)-cnt)
} else {
k := 0
for i := range s {
k++
if i == len(s)-1 || s[i] != s[i+1] {
cnt += k / (m + 1)
k = 0
}
}
}
return cnt <= numOps
}
return 1 + sort.Search(len(s), func(m int) bool { return check(m) })
}Complexity analysis
| 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 |
Frequently asked questions
Is Smallest Substring With Identical Characters I easy or hard?
The problem is labeled Hard because it requires recognizing the monotonic property that enables binary search on the answer. The implementation itself is moderate once you derive the formula for splitting long runs and counting required operations.
Smallest Substring With Identical Characters I Python/Java solution
Implement binary search over the answer and write a helper function that scans the string to count required modifications for a given limit L. The same logic works across Python, Java, C++, Go, and TypeScript because it only uses loops, counters, and integer division.
How to solve Smallest Substring With Identical Characters I in O(n)?
A pure O(n) solution is generally not used because the target maximum substring length is unknown. Instead, binary search narrows the answer range while each check runs in O(n). The combined complexity becomes O(n log n), which is efficient for large inputs.
What is the best approach for Smallest Substring With Identical Characters I?
Binary search on the maximum allowed substring length combined with a linear run-length check. For each candidate length L, count how many character modifications are needed to break runs longer than L using floor(run / (L + 1)). The smallest L that requires at most k changes is the answer. This runs in O(n log n) time and O(1) space.
Is Smallest Substring With Identical Characters I asked at Google/Amazon/Meta?
Problems combining binary search on the answer with string run analysis frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of minimizing the longest repeating segment or splitting runs with limited operations are common interview patterns.
What data structure is used in Smallest Substring With Identical Characters I?
No complex data structure is required. The solution relies on simple string or array traversal to compute run lengths, combined with binary search to optimize the maximum allowed substring length.
What is the time complexity of Smallest Substring With Identical Characters I?
The optimal solution runs in O(n log n) time. Binary search explores the range of possible maximum substring lengths, and each feasibility check scans the string once to compute required modifications. Space complexity is O(1) since only counters and pointers are used.