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

思路

滑动窗口检验是否超过k，显然右端点非单调递减

Solutions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n=s.size();
        vector<array<int,2>>v(n+1);
        for(int i=1;i<=n;++i){
            v[i][0]=v[i-1][0]+(s[i-1]=='0');
            v[i][1]=v[i-1][1]+(s[i-1]=='1');
        }
        int ans=0;
        for(int i=1,j=1;i<=n&&i<=j;++i){
            while(i<=n&&j<=n&&((v[j][0]-v[i-1][0]<=k)||(v[j][1]-v[i-1][1]<=k)))j++;
            ans+=j-i;
        }
        return ans;
    }
};