Input: s ="000001", numOps =1Output: 2Explanation:
By changing `s[2]` to `'1'`,`s` becomes `"001001"`. The longest substrings
with identical characters are `s[0..1]` and `s[3..4]`.
To minimize the length of the longest substring of identical characters after at most numOps flips, we can use binary search on the answer. For each possible length, we check if we can break all runs of length > mid by flipping at most numOps bits. This can be checked efficiently using a sliding window.
classSolution {
public:int minLength(string s, int k) {
int n = s.size(), ans = n;
auto check = [&](int m, char ch) {
int cnt =0;
for (int i =0; i < m; ++i) cnt += s[i] != ch;
if (cnt <= k) return true;
for (int i = m; i < n; ++i) {
cnt += s[i] != ch;
cnt -= s[i-m] != ch;
if (cnt <= k) return true;
}
return false;
};
int l =1, r = n;
while (l <= r) {
int m = (l + r) /2;
if (check(m, '0') || check(m, '1')) { ans = m; r = m -1; }
else l = m +1;
}
return ans;
}
};
classSolution {
publicintminLength(String s, int k) {
int n = s.length(), ans = n;
int l = 1, r = n;
while (l <= r) {
int m = (l + r) / 2;
if (check(s, m, k, '0') || check(s, m, k, '1')) { ans = m; r = m - 1; }
else l = m + 1;
}
return ans;
}
privatebooleancheck(String s, int m, int k, char ch) {
int cnt = 0, n = s.length();
for (int i = 0; i < m; ++i) if (s.charAt(i) != ch) cnt++;
if (cnt <= k) returntrue;
for (int i = m; i < n; ++i) {
if (s.charAt(i) != ch) cnt++;
if (s.charAt(i-m) != ch) cnt--;
if (cnt <= k) returntrue;
}
returnfalse;
}
}
classSolution {
funminLength(s: String, k: Int): Int {
val n = s.length
var ans = n
funcheck(m: Int, ch: Char): Boolean {
var cnt = 0for (i in0 until m) if (s[i] != ch) cnt++if (cnt <= k) returntruefor (i in m until n) {
if (s[i] != ch) cnt++if (s[i-m] != ch) cnt--if (cnt <= k) returntrue }
returnfalse }
var l = 1; var r = n
while (l <= r) {
val m = (l + r) / 2if (check(m, '0') || check(m, '1')) { ans = m; r = m - 1 }
else l = m + 1 }
return ans
}
}
classSolution:
defminLength(self, s: str, k: int) -> int:
n, ans = len(s), len(s)
defcheck(m: int, ch: str) -> bool:
cnt = sum(1for i in range(m) if s[i] != ch)
if cnt <= k: returnTruefor i in range(m, n):
cnt += s[i] != ch
cnt -= s[i-m] != ch
if cnt <= k: returnTruereturnFalse l, r =1, n
while l <= r:
m = (l + r) //2if check(m, '0') or check(m, '1'):
ans = m
r = m -1else:
l = m +1return ans
impl Solution {
pubfnmin_length(s: String, k: i32) -> i32 {
let n = s.len();
let s = s.as_bytes();
letmut ans = n asi32;
letmut l =1;
letmut r = n asi32;
let check =|m: i32, ch: u8| -> bool {
letmut cnt =0;
for i in0..m { if s[i asusize] != ch { cnt +=1; } }
if cnt <= k { returntrue; }
for i in m..n asi32 {
if s[i asusize] != ch { cnt +=1; }
if s[(i-m) asusize] != ch { cnt -=1; }
if cnt <= k { returntrue; }
}
false };
while l <= r {
let m = (l + r) /2;
if check(m, b'0') || check(m, b'1') { ans = m; r = m -1; }
else { l = m +1; }
}
ans
}
}