【Leetcode Daily】3258统计满足K约束的子字符串数量I

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，给一个由 0 和 1 组成的字符串，求其中所有的子字符串数量，但子字符串必须满足 0 或 1 最多为 K 的限制。

思路分享

• 简单的越短越合法类型的不定长滑动窗口，直接使用例题思路即可，【Leetcode Daily】713乘积小于K的子数组。

• 参考灵神的题解，可以用与 1的方式来实现对字母’0’，’1’的区分，毕竟本质上两个字母一个是奇数，一个是偶数，与 1 后直接映射到 0 和 1 上，具体映射哪个也不重要，反正题目也并不区分 0 和 1 的限制方式。

  https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/solutions/2884495/on-hua-dong-chuang-kou-pythonjavacgo-by-keubv/

代码解答（强烈建议自行解答后再看）

• 参考解法

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int rec[2]{};
        int left = 0, ans = 0;
        for(int right = 0; right < s.size(); right++) {
            rec[s[right]-'0']++;
            while(rec[0] > k && rec[1] > k) {
                rec[s[left++]-'0']--;
            }
            //cout << left << " " << right << " " << s.substr(left, right-left+1) << endl;
            ans += right-left+1;
        }
        return ans;
    }
};