leetcode3261

Posted on

题目

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
  • 所有查询互不相同

题解

对于每一个查询$q=[l,r]$,我们希望于经过某种预处理后，实现$O(1)$回答查询，我们用区间$[l,r]$替代其叙述的子串$s[l\dots r]$；

规定某种布尔变量$\delta$，记录区间$[l,r]$是否为$k$约束的
$$
\delta(u,v)=\begin{cases}
1&\text{[l,r]是k约束的；}\
0&\text{Otherwise.}
\end{cases}
$$
观察任意一个区间,应该具有如下先验性质：

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

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

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

  • 对于固定的右端点$j$，若$[i,j]$不是$k$约束的，左移端点$i$，可能变为$k$约束的（因为$[j,j]$被认为一定是$k$约束的，$\forall k$）;找到这种极大区间$[f(j),j]$：

    可建立映射$f:0\le f(j)\le j$,其中$[0,j],\cdots,[f(j)-1, j]$不是$k$约束的，$[f(j),j],\cdots,[j,j]$是$k$约束的;

  • 对于固定的左端点$i$，若$[i,j]$是$k$约束的，右移端点$j$，可能变为不是$k$约束的（因为越界的区间$[i,n]$不认为是$k$约束的），找到这种极大区间$[i,g(i)]$：

    建立映射$g:i<g(i)\le n$,其中$[i,i],\cdots,[i,g(i)-1]$是$k$约束的，$[i,g(i)],\cdots,[i,n]$不是$k$约束的；

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

左移端点的同时应该维护一个区间长度的前缀和$\rm{prefix}$
$$
{\rm prefix}(j+1)=\sum_{t=0}^r \sum_{u=f(t)}^t 1=\sum_{t=0}^j (t-f(t)+1)
$$
[对于查询$[l,r]$,查询的答案是
$$
\begin{aligned}
\sum_{(u,v)\sube [l,r]} \delta(u,v)
&=\sum_{v=l}^r \sum_{u=l}^v \delta(u,v)\
&=\sum_{v=l}^{g(i)-1}\sum_{u=l}^v 1 + \sum_{v=g(i)}^r \sum_{u=f(v)}^v 1\
&=\frac{(g(i)-i)(g(i)-i+1)}{2} + {\rm prefix}(r+1)-{\rm prefix}(g(i))
\end{aligned}
$$
更新映射数组$f,g$，其具有某种单调性，可以采用滑动窗口更新；

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
    }
};