当前位置：首页 > news >正文

LeetCode 每日一题统计满足 K 约束的子字符串数量 I

news 2024/11/15 2:13:02

统计满足 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 约束。

题解

需要统计所有满足条件的子串

由于子串的长度是不定的，所以不能直接用到滑动窗口去遍历

我们可以枚举子串的右端点 i ，寻找以 i 为右端点的子串有多少满足条件

将 i 从 0 遍历到字符串长度的 n-1 就可以找到所有满足条件的子串

只要某一点为左端点的子串满足条件，那么从这个左端点到右端点的所有点都可以作为子串的左端点并且满足条件

所以我们需要找到对于右端点 i 满足条件的最小左端点

根据题意，我们不难发现，只要子串的长度越小，就越有可能满足条件

也就是说，当 i 越大，满足的最小左端点就越大

最小左端点是单调的

也就是说，最小左端点只能增大

所以我们就可以使用滑动窗口来维护子串

对于一个右端点 i
如果此时的最小最左端点 l 与右端点形成的子串满足条件
则说明右端点为 i 的满足条件的子串有 r-l+1 个
如果此时最小最左端点 l 与右端点形成的子串不满足条件
则 l++，直到满足条件
右端点为 i 的满足条件的子串有 r-l+1 个

代码如下↓

int countKConstraintSubstrings(char* s, int k) {int l=0;int res=0;int a0=0;int a1=0;int n=strlen(s);for(int i=0;i<n;i++){if(s[i]=='0'){a0++;}else{a1++;}while(a0>k && a1>k){if(s[l]=='0'){a0--;}else{a1--;}l++;}res+=i-l+1;}return res;
}