Smallest Substring With Identical Characters I
HardUpdated: Jul 27, 2025
Practice on:
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.
Examples
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
Solution
Method 1 – Binary Search on Substring Length
Intuition
We use binary search to find the minimum possible length of the longest substring with identical characters after performing at most numOps flips. For each candidate length, we check if it's possible to achieve using the allowed operations.
Approach
- Apply binary search on possible substring lengths from 1 to
n. - For each candidate length
mid, use anisValidfunction to check if it's achievable:- If
mid == 1, try to convert the string to alternating '0' and '1' patterns, counting mismatches for both starting characters. - If
mid > 1, count the length of each run of identical characters. For each run longer thanmid, calculate the number of flips needed to break it into smaller segments (usingcount // (mid + 1)).
- If
- If a length is valid, update the answer and search for a smaller length; otherwise, search for a larger length.
Complexity
- ⏰ Time complexity:
O(n log n), due to binary search and linear scan for each candidate length. - 🧺 Space complexity:
O(1), only constant extra space is used.
Code
C++
class Solution {
public:
int minLength(string s, int numOps) {
int n = s.size(), left = 1, right = n, ans = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isValid(s, numOps, mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
bool checkAlternating(const string& s, int numOps, char startChar) {
int opsNeeded = 0;
char expected = startChar;
for (char c : s) {
if (c != expected) opsNeeded++;
expected = (expected == '0') ? '1' : '0';
}
return opsNeeded <= numOps;
}
bool isValid(const string& s, int numOps, int mid) {
if (mid == 1) {
return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
}
int opsNeeded = 0, count = 1;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == s[i-1]) {
count++;
} else {
opsNeeded += count / (mid + 1);
count = 1;
}
}
opsNeeded += count / (mid + 1);
return opsNeeded <= numOps;
}
};
Java
class Solution {
public int minLength(String s, int numOps) {
int n = s.length();
int left = 1, right = n, ans = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isValid(s, numOps, mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
private boolean checkAlternating(String s, int numOps, char startChar) {
int opsNeeded = 0;
char expected = startChar;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != expected) opsNeeded++;
expected = (expected == '0') ? '1' : '0';
}
return opsNeeded <= numOps;
}
private boolean isValid(String s, int numOps, int mid) {
if (mid == 1) {
return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
}
int opsNeeded = 0, count = 1;
for (int i = 1; i < s.length(); ++i) {
if (s.charAt(i) == s.charAt(i-1)) {
count++;
} else {
opsNeeded += count / (mid + 1);
count = 1;
}
}
opsNeeded += count / (mid + 1);
return opsNeeded <= numOps;
}
}
Go
func minLength(s string, numOps int) int {
n := len(s)
left, right, ans := 1, n, n
for left <= right {
mid := left + (right-left)/2
if isValid(s, numOps, mid) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
func checkAlternating(s string, numOps int, startChar byte) bool {
opsNeeded := 0
expected := startChar
for i := 0; i < len(s); i++ {
if s[i] != expected {
opsNeeded++
}
if expected == '0' {
expected = '1'
} else {
expected = '0'
}
}
return opsNeeded <= numOps
}
func isValid(s string, numOps, mid int) bool {
if mid == 1 {
return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1')
}
opsNeeded, count := 0, 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
count++
} else {
opsNeeded += count / (mid + 1)
count = 1
}
}
opsNeeded += count / (mid + 1)
return opsNeeded <= numOps
}
Kotlin
class Solution {
fun minLength(s: String, numOps: Int): Int {
var left = 1
var right = s.length
var ans = s.length
while (left <= right) {
val mid = left + (right - left) / 2
if (isValid(s, numOps, mid)) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
private fun checkAlternating(s: String, numOps: Int, startChar: Char): Boolean {
var opsNeeded = 0
var expected = startChar
for (c in s) {
if (c != expected) opsNeeded++
expected = if (expected == '0') '1' else '0'
}
return opsNeeded <= numOps
}
private fun isValid(s: String, numOps: Int, mid: Int): Boolean {
if (mid == 1) {
return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1')
}
var opsNeeded = 0
var count = 1
for (i in 1 until s.length) {
if (s[i] == s[i-1]) {
count++
} else {
opsNeeded += count / (mid + 1)
count = 1
}
}
opsNeeded += count / (mid + 1)
return opsNeeded <= numOps
}
}
Python
class Solution:
def minLength(self, s: str, numOps: int) -> int:
def check_alternating(s, numOps, start_char):
ops_needed = 0
expected = start_char
for c in s:
if c != expected:
ops_needed += 1
expected = '1' if expected == '0' else '0'
return ops_needed <= numOps
def is_valid(s, numOps, mid):
if mid == 1:
return check_alternating(s, numOps, '0') or check_alternating(s, numOps, '1')
ops_needed, count = 0, 1
for i in range(1, len(s)):
if s[i] == s[i-1]:
count += 1
else:
ops_needed += count // (mid + 1)
count = 1
ops_needed += count // (mid + 1)
return ops_needed <= numOps
n = len(s)
left, right, ans = 1, n, n
while left <= right:
mid = left + (right - left) // 2
if is_valid(s, numOps, mid):
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
Rust
impl Solution {
pub fn min_length(s: String, num_ops: i32) -> i32 {
fn check_alternating(s: &str, num_ops: i32, start_char: char) -> bool {
let mut ops_needed = 0;
let mut expected = start_char;
for c in s.chars() {
if c != expected {
ops_needed += 1;
}
expected = if expected == '0' { '1' } else { '0' };
}
ops_needed <= num_ops
}
fn is_valid(s: &str, num_ops: i32, mid: i32) -> bool {
if mid == 1 {
return check_alternating(s, num_ops, '0') || check_alternating(s, num_ops, '1');
}
let mut ops_needed = 0;
let mut count = 1;
let s_bytes = s.as_bytes();
for i in 1..s.len() {
if s_bytes[i] == s_bytes[i-1] {
count += 1;
} else {
ops_needed += count / (mid + 1);
count = 1;
}
}
ops_needed += count / (mid + 1);
ops_needed <= num_ops
}
let n = s.len() as i32;
let mut left = 1;
let mut right = n;
let mut ans = n;
while left <= right {
let mid = left + (right - left) / 2;
if is_valid(&s, num_ops, mid) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
ans
}
}
TypeScript
class Solution {
minLength(s: string, numOps: number): number {
const checkAlternating = (s: string, numOps: number, startChar: string): boolean => {
let opsNeeded = 0;
let expected = startChar;
for (let i = 0; i < s.length; i++) {
if (s[i] !== expected) opsNeeded++;
expected = expected === '0' ? '1' : '0';
}
return opsNeeded <= numOps;
};
const isValid = (s: string, numOps: number, mid: number): boolean => {
if (mid === 1) {
return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
}
let opsNeeded = 0, count = 1;
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i-1]) {
count++;
} else {
opsNeeded += Math.floor(count / (mid + 1));
count = 1;
}
}
opsNeeded += Math.floor(count / (mid + 1));
return opsNeeded <= numOps;
};
let left = 1, right = s.length, ans = s.length;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (isValid(s, numOps, mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}