题目描述
给你一个 二进制 字符串 s
和一个整数 k
。
如果一个 二进制字符串 满足以下任一条件,则认为该字符串满足 k 约束:
- 字符串中
0
的数量最多为 k
。
- 字符串中
1
的数量最多为 k
。
返回一个整数,表示 s
的所有满足 k 约束 的子字符串的数量。
示例 1:
输入:s = "10101", k = 1
输出:12
解释:
s
的所有子字符串中,除了 "1010"
、"10101"
和 "0101"
外,其余子字符串都满足 k 约束。
示例 2:
输入:s = "1010101", k = 2
输出:25
解释:
s
的所有子字符串中,除了长度大于 5 的子字符串外,其余子字符串都满足 k 约束。
示例 3:
输入:s = "11111", k = 1
输出:15
解释:
s
的所有子字符串都满足 k 约束。
提示:
1 <= s.length <= 50
1 <= k <= s.length
s[i]
是 '0'
或 '1'
。
解法
方法一:滑动窗口
我们用两个变量 $\textit{cnt0}$ 和 $\textit{cnt1}$ 分别记录当前窗口内的 $0$ 和 $1$ 的个数,用 $\textit{ans}$ 记录满足 $k$ 约束的子字符串的个数,用 $l$ 记录窗口的左边界。
当我们右移窗口时,如果窗口内的 $0$ 和 $1$ 的个数都大于 $k$,我们就需要左移窗口,直到窗口内的 $0$ 和 $1$ 的个数都不大于 $k$。此时,窗口内的所有子字符串都满足 $k$ 约束,个数为 $r - l + 1$,其中 $r$ 是窗口的右边界。我们将这个个数累加到 $\textit{ans}$ 中。
最后,我们返回 $\textit{ans}$ 即可。
时间复杂度 $O(n)$,其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def countKConstraintSubstrings(self, s: str, k: int) -> int:
cnt0 = cnt1 = 0
ans = l = 0
for r, c in enumerate(s):
cnt0 += int(c) ^ 1
cnt1 += int(c)
while cnt0 > k and cnt1 > k:
cnt0 -= int(s[l]) ^ 1
cnt1 -= int(s[l])
l += 1
ans += r - l + 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public int countKConstraintSubstrings(String s, int k) {
int cnt0 = 0, cnt1 = 0;
int ans = 0, l = 0;
for (int r = 0; r < s.length(); ++r) {
int x = s.charAt(r) - '0';
cnt0 += x ^ 1;
cnt1 += x;
while (cnt0 > k && cnt1 > k) {
int y = s.charAt(l++) - '0';
cnt0 -= y ^ 1;
cnt1 -= y;
}
ans += r - l + 1;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
int cnt0 = 0, cnt1 = 0;
int ans = 0, l = 0;
for (int r = 0; r < s.length(); ++r) {
int x = s[r] - '0';
cnt0 += x ^ 1;
cnt1 += x;
while (cnt0 > k && cnt1 > k) {
int y = s[l++] - '0';
cnt0 -= y ^ 1;
cnt1 -= y;
}
ans += r - l + 1;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | func countKConstraintSubstrings(s string, k int) (ans int) {
cnt0, cnt1, l := 0, 0, 0
for r, c := range s {
x := int(c - '0')
cnt0 += x ^ 1
cnt1 += x
for cnt0 > k && cnt1 > k {
y := int(s[l] - '0')
cnt0 -= y ^ 1
cnt1 -= y
l++
}
ans += r - l + 1
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function countKConstraintSubstrings(s: string, k: number): number {
let [cnt0, cnt1, ans, l] = [0, 0, 0, 0];
for (let r = 0; r < s.length; ++r) {
const x = s[r] === '1' ? 1 : 0;
cnt0 += x ^ 1;
cnt1 += x;
while (cnt0 > k && cnt1 > k) {
const y = s[l++] === '1' ? 1 : 0;
cnt0 -= y ^ 1;
cnt1 -= y;
}
ans += r - l + 1;
}
return ans;
}
|