leetcode3261

题目

leetcode3261

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

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

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

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

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

子字符串

的数量。

示例 1：

**输入：**s = "0001111", k = 2, queries = [[0,6]]

输出：[26]

解释：

对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。

示例 2：

**输入：**s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]

输出：[15,9,3]

解释：

s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

提示：

1 <= s.length <= 105
s[i] 是 '0' 或 '1'
1 <= k <= s.length
1 <= queries.length <= 105
queries[i] == [li, ri]
0 <= li <= ri < s.length
所有查询互不相同

题解

对于每一个查询,我们希望于经过某种预处理后，实现回答查询，我们用区间替代其叙述的子串；

规定某种布尔变量，记录区间是否为约束的

观察任意一个区间,应该具有如下先验性质：

若区间是约束的，那么其子区间也应该是约束的；
若区间不是约束，那么其超区间也不应该是约束的；

回忆关联规则挖掘中的频繁项集，似乎也具有这样的先验性质；

考察某种约束的区间,他应该具有极大性质的区间，类似于极大频繁项集在Apriori算法的作用：

对于固定的右端点，若不是约束的，左移端点，可能变为约束的（因为被认为一定是约束的，）;找到这种极大区间：

可建立映射,其中不是约束的，是约束的;
对于固定的左端点，若是约束的，右移端点，可能变为不是约束的（因为越界的区间不认为是约束的），找到这种极大区间：

建立映射,其中是约束的，不是约束的；

注意，这样的映射建立的本质原因是因为不可能存在两个数满足对应性质；

左移端点的同时应该维护一个区间长度的前缀和

[对于查询,查询的答案是

更新映射数组，其具有某种单调性，可以采用滑动窗口更新；

AC代码

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> count(2, 0);
        vector<int> g(n, n);
        vector<long long> prefix(n + 1, 0);
        int i = 0;
        for (int j = 0; j < n; ++j) {
            count[s[j] - '0']++;
            while (count[0] > k && count[1] > k) {
                count[s[i] - '0']--;
                g[i] = j;
                i++;
            }
            prefix[j + 1] = prefix[j] + j - i + 1;
        }

        vector<long long> res;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            int i = min(g[l], r + 1);
            long long part1 = 1LL * (i - l + 1) * (i - l) / 2;
            long long part2 = prefix[r + 1] - prefix[i];
            res.push_back(part1 + part2);
        }
        return res;
    }
};