一、题目描述
给你一个 二进制 字符串 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’。
二、解题思路
这道题目可以利用了滑动窗口的技巧来维护一个动态的子串区间 [l, i]，并确保窗口内的 ‘1’ 和 ‘0’ 的数量都不超过 k。滑动窗口可以高效地解决这种类型的子串计数问题。
- 当窗口内的 ‘1’ 或 ‘0’ 的数量超过 k 时，窗口左边（l）会被向右移动，直到窗口变得有效。
- 每当窗口有效时，表示从 l 到 i 的子串都符合条件，因此将它们的数量（即 i - l + 1）加到结果中。
三、代码
class Solution {
public:int countKConstraintSubstrings(string s, int k) {int l = 0;int count = 0;int one = 0;int zero = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '1') one++;else zero++;while (one > k && zero > k) {if (s[l++] == '1') one--;else zero--;}count += i - l + 1;}return count;}
};
