3258. 统计满足 K 约束的子字符串数量 I

题目链接

解题思路

• 小字符串不满足了，那么包含此小字符串的大字符串肯定不满足。
• 大字符串满足，那么该字符串的所有子串都满足条件。所以，我们就可以把问题转成，「以i开头的字符串，满足条件的，最长多长？」然后再根据这个结果，计算以i开头的所有子串数目即可。
• 计算了「以i开头的最长的结果」，怎么计算「以i+1开头的最长的结果」？滑动窗口，假设以i开头结果是[i, j]，窗口大小就是[i, j]，此时，把i移出窗口，看右侧窗口是否还能扩大。

代码

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int j = -1;
        int ans = 0;
        int n = s.length();
        int oneNums = 0;
        int zeroNums = 0;
        for (int i = 0; i < n; ++i) {
            // 把 i - 1移出窗口
            if (i > 0) {
                switch (s[i - 1]) {
                    case '0':
                        zeroNums--;
                    break;
                    case '1':
                        oneNums--;
                    break;
                }
            }
            // 右侧窗口能扩吗？
            while(j + 1 < n) {
                if (s[j + 1] == '0') {
                    if (zeroNums < k || oneNums <= k) {
                        j++;
                        zeroNums++;    
                    } else {
                        break;
                    }
                } else if (s[j + 1] == '1' ) {
                    if (oneNums < k || zeroNums <= k) {
                        j++;
                        oneNums++;    
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
            // 计算结果
            ans += j - i + 1;
        }
        return ans;
    }
};