力扣每日一题 3261. 统计满足 K 约束的子字符串数量 II

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的 子字符串的数量。

今天的题目作为昨天的进阶，不仅数据范围变大了，单次查询也变成了多次查询。难度高了很多。

我现在已经懒到写题目都不想动笔算了。但事实证明有的时候该动笔还是得动笔算一下的。

这个题思路很简单，实际上就是单纯的一个尺取或者是滑动窗口。如果要把前缀和当成一种算法的话，那就是再加个前缀和而已。

首先我们要知道两件事。

1. 如果子串[l,r]是合法子串(即满足k约束)，那么[l,r]内的所有子串一定都是合法的。

2. [0,r]的所有的合法子串的数量等于右端点为 i 的所有合法子串的和。0<=i<=r。或者说[0,r]的任一合法子串的右端点一定是在[0,r]之间的。

那么，如果对于左端点 l ，最长的合法子串的右端点r1，那么对于区间[l,r]，如果r<=r1，那显然[l,r]的合法子串的数量就是[l,r]的所有子串。

举个例子，假设k=3, s[0,8]="001110001"。对于所有左端点为0的子串，最长的合法子串是s[0,7]="00111000"。那么，如果我们要求[0,6]的合法子串数量，[0,6]内的所有子串都是合法的。

当然，对于左端点不为0的情况也是同样适用的。

可是，假如区间[l,r]的r>=r1呢？很简单，分成[0,r1],[r1+1,r]两个部分计算就可以了。前面的部分直接算所有子串数量就可以了。可后面[r1+1,r]的子串数量呢？我们可以把所有右端点在[r1+1,r]的合法子串算出来求和。这样做会不会有重复或者遗漏或者多算的吗？当然并不会。

1. [l,r]计算了所有右端点在[l,r1]的合法子串，所有我们计算的[r1+1,r]的合法子串并不会和前面的有重复，毕竟子串的右端点不一样了。

2. 区间[l,r]的所有合法子串的右端点一定在[l,r]之间，而我们计算了所有右端点在[l,r1]的合法子串和所有右端点在[r1+1,r]的合法子串，刚好把整个区间[l,r]覆盖了，所以也不会有遗漏。

3. 因为左端点为 l 的最长的合法子串是[l,r1],所以[l,r1+1]一定是不合法的，以r1+1为右端点的最长的合法子串的左端点一定在 l 的右边。也就是说所有右端点在[r1+1,r]的合法子串的左端点一定落在(l,r1+1]。所以也不会有多算的情况。这里也许表达的不是那么清楚，但稍微想想应该能明白。

所以现在的问题就是我们怎么计算以某个位置为右端点的合法子串的数量了。还是以k=3, s[0,8]="001110001"为例。我们知道了所有左端点为0的子串，最长的合法子串是s[0,7]="00111000"。其实就是说所有以7为右端点的合法子串，最长的合法子串是s[0...7]。很显然，s[0...7], s[1...7], s[2...7],..., s[7,7]就是答案了，数量为 7-0+1=8.

也就是说我们只要求出来以 r 为右端点的最长的合法子串的左端点 l 就可以直接算出来以r为右端点的所有合法子串的数量了。如果只是求一个，那直接遍历就可以了，但现在我们需要把[0,s.length]的每个位置都求一遍，两重循环暴力肯定会超时，怎么办？那就用滑动窗口咯。没学过的自行百度。或者参考灵神的题解视频。

下面是代码。right[i] 表示以 i 为左端点的最长的合法子串的右端点。

prefix[i]表示以 i 为右端点的所有合法子串的数量  的前缀和。这样在求[r1+1,r]的合法子串数量的时候就可以一个减法prefix[r]-prefix[r1]完成了，不需要再遍历一遍[r1+1,r]求和了

#define ll long long
class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n = s.length();
        ll prefix[n+5];
        int right[n+5];
        for (int i=0; i<n+5; i++)
        {
            prefix[i]=0, right[i]=n-1;
        }
        prefix[0]=1;
        int num[2]={0,0};
        int st=0;
        for (int ed=0; ed<n; ++ed)
        {
            ++num[s[ed]-'0'];
            while (num[0]>k && num[1]>k)
            {
                right[st]=ed-1;
                --num[s[st]-'0'];
                st++;
            }
            if (ed) prefix[ed]=prefix[ed-1]+ed-st+1;
        }
        // for(int i=0; i<n;++i) printf("%d ", prefix[i]);printf("\n");
        // for(int i=0; i<n;++i) printf("%d ", right[i]);printf("\n");
        vector<ll> ans;
        for(auto vec:queries)
        {
            int l=vec[0], r=vec[1], rl=right[l];
            // printf("l=%d, r=%d, rl=%d\n", l, r, rl);
            ll len=min(rl, r)-l+1;
            ll x = len*(len+1)/2;
            if (right[l] >= r)
            {
                ans.push_back(x);
            }
            else
            {
                ans.push_back(x+prefix[r]-prefix[rl]);
                // printf("x=%d, r=%d, rl-1=%d\n", x, prefix[r], prefix[rl]);
            }
        }
        return ans;
    }
};

预处理求right和prefix的时间复杂度O(n)，单次查询的时间复杂度O(1).总时间复杂度O(n+m).n表示s的长度，m表示查询的次数。

空间复杂度O(n)