class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
}
};
100402. 统计满足 K 约束的子字符串数量 I
给你一个 二进制 字符串 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 <= 501 <= k <= s.lengths[i] 是 '0' 或 '1'。原站题解
typescript 解法, 执行用时: 3 ms, 内存消耗: 52.4 MB, 提交时间: 2024-11-12 09:49:03
function countKConstraintSubstrings(s: string, k: number): number {
const cnt: [number, number] = [0, 0];
let [ans, l] = [0, 0];
for (let r = 0; r < s.length; ++r) {
cnt[+s[r]]++;
while (cnt[0] > k && cnt[1] > k) {
cnt[+s[l++]]--;
}
ans += r - l + 1;
}
return ans;
}
php 解法, 执行用时: 7 ms, 内存消耗: 20.2 MB, 提交时间: 2024-08-19 10:17:48
class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function countKConstraintSubstrings($s, $k) {
$cnt = [0, 0]; // 用于计数0和1的数组
$left = 0; // 滑动窗口的左边界
$ans = 0; // 存储结果
for ($i = 0; $i < strlen($s); $i++) {
// 根据当前字符是'0'还是'1'来更新计数器
$cnt[intval($s[$i])]++;
// 当两个计数器都超过k时，移动左指针
while ($cnt[0] > $k && $cnt[1] > $k) {
$cnt[intval($s[$left])]--;
$left++;
}
// 更新答案：以当前字符结尾的满足条件的子字符串数量
// 等于 $i - $left + 1，因为左指针之前的所有字符都可以作为子字符串的起始位置
$ans += $i - $left + 1;
}
return $ans;
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 51.6 MB, 提交时间: 2024-08-19 10:16:12
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var countKConstraintSubstrings = function(s, k) {
let cnt = [0, 0]; // 用于计数0和1的数组
let left = 0; // 滑动窗口的左边界
let ans = 0; // 存储结果
for (let i = 0; i < s.length; i++) {
// 根据当前字符是'0'还是'1'来更新计数器
cnt[s.charCodeAt(i) - '0'.charCodeAt(0)]++;
// 当两个计数器都超过k时，移动左指针
while (cnt[0] > k && cnt[1] > k) {
cnt[s.charCodeAt(left) - '0'.charCodeAt(0)]--;
left++;
}
// 更新答案：以当前字符结尾的满足条件的子字符串数量
// 等于i - left + 1，因为左指针之前的所有字符都可以作为子字符串的起始位置
ans += i - left + 1;
}
return ans;
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-08-19 10:14:35
impl Solution {
pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
let bytes = s.as_bytes(); // 将字符串转换为字节切片
let mut cnt = [0i32; 2]; // 使用i32数组来计数
let mut left = 0;
let mut ans = 0i32;
for (i, &byte) in bytes.iter().enumerate() {
cnt[(byte & 1) as usize] += 1;
// 当两个计数器都超过k时，移动左指针
while cnt[0] > k && cnt[1] > k {
cnt[(bytes[left] & 1) as usize] -= 1;
left += 1;
}
// 更新答案
ans += (i - left + 1) as i32;
}
ans
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 8.5 MB, 提交时间: 2024-08-19 10:10:56
class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
int ans = 0, left = 0, cnt[2]{};
for (int i = 0; i < s.length(); i++) {
cnt[s[i] & 1]++;
while (cnt[0] > k && cnt[1] > k) {
cnt[s[left++] & 1]--;
}
ans += i - left + 1;
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 41.4 MB, 提交时间: 2024-08-19 10:10:28
class Solution {
public int countKConstraintSubstrings(String S, int k) {
char[] s = S.toCharArray();
int ans = 0;
int left = 0;
int[] cnt = new int[2];
for (int i = 0; i < s.length; i++) {
cnt[s[i] & 1]++;
while (cnt[0] > k && cnt[1] > k) {
cnt[s[left++] & 1]--;
}
ans += i - left + 1;
}
return ans;
}
}
python3 解法, 执行用时: 46 ms, 内存消耗: 16.5 MB, 提交时间: 2024-08-19 10:10:15
class Solution:
def countKConstraintSubstrings(self, s: str, k: int) -> int:
ans = left = 0
cnt = [0, 0]
for i, c in enumerate(s):
cnt[ord(c) & 1] += 1
while cnt[0] > k and cnt[1] > k:
cnt[ord(s[left]) & 1] -= 1
left += 1
ans += i - left + 1
return ans
golang 解法, 执行用时: 6 ms, 内存消耗: 2.3 MB, 提交时间: 2024-08-19 10:09:55
// 滑动窗口
func countKConstraintSubstrings(s string, k int) (ans int) {
cnt := [2]int{}
left := 0
for i, c := range s {
cnt[c&1]++
for cnt[0] > k && cnt[1] > k {
cnt[s[left]&1]--
left++
}
ans += i - left + 1
}
return
}