3261. 统计满足 K 约束的子字符串数量 II

题解

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k,
                                                 vector<vector<int>>& queries) {
        int n = s.size();
        vector<long long> ret(queries.size());
        vector<int> left(n);          // 记录以i为右端点，最小的left位置
        vector<long long> sum(n + 1); // 计算left前缀和
        int l = 0, cnt[2] = {};
        for (int i = 0; i < s.size(); i++) {
            cnt[s[i] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l] & 1]--;
                l++;
            }
            left[i] = l;
            sum[i + 1] = sum[i] + i - l + 1;
        }

        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0], r = queries[i][1];
            // 满足右端为r的left比l更小，表示全部满足，计算1到r-l+1的累加和即可
            if (left[r] <= l) 
                ret[i] = (long long)(r - l + 2) * (r - l + 1) / 2;
            // 满足右端为r的left比l大，表示部分满足，只需找到这个可以满足的位置j，在做1到j-l的累加和
            else { 
                int j = lower_bound(left.begin() + l, left.begin() + r + 1, l) -
                        left.begin();
                ret[i] =
                    sum[r + 1] - sum[j] + (long long)(j - l + 1) * (j - l) / 2;
            }
        }
        return ret;
    }
};

思路

滑动窗口、前缀和

使用滑动窗口思想，右指针“扩展”，左指针“收紧”寻找满足条件的left，得到left数组。

同时对left数组计算前缀和，用于优化计算

二分查找

在查找的范围中，不是任意子序列都满足要求时，为了在left数组（是升序的）中快速找到满足的值，采用二分查找来优化搜索。