Description
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 (where 0 <= i < n) and flip s[i], i.e., 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.
A substring is a contiguous non-empty sequence of characters within a string.
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 <= n
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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) })
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | 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;
}
|