3297 统计重新排列后包含另一个字符串的子字符串数目 I & II

题目链接

3297. 统计重新排列后包含另一个字符串的子字符串数目 I

3298. 统计重新排列后包含另一个字符串的子字符串数目 II

分析

滑动窗口

我们首先统计 $word2$ 中出现的字符的个数，使用滑动窗口去对比 $word1$ 中的每一个子字符串

令 $n$ 为 $word1$ 的长度，从 $word1[0]$ 开始，向右扩展滑动窗口右边界 $r$，直到窗口里的字符串满足题目条件

那么这时，以 $word1[0]$ 为左边界，以 $r, r+1, \cdots ,n$ 为右边界的子字符串均满足条件，共 $n - r + 1$ 个

接下来将左边界 $l$ 右移一位后，继续向右扩展右边界 $r$ ，重复该过程进行计算即可

代码实现

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        if(word1.size() < word2.size()) {
            return 0;
        }

        long long ans = 0;
        vector<int> diff(26, 0);

        for(char c : word2){
            diff[c - 'a']--;
        }

        int cnt = count_if(diff.begin(), diff.end(), [](int x) {return x < 0;});

        auto update = [&](int x, int y) {
            diff[x] += y;
            if(y == 1 && diff[x] == 0) {
                cnt--;
            }
            else if(y == -1 && diff[x] == -1) {
                cnt++;
            }
        };

        int n = word1.size();

        for(int l = 0, r = 0; l < n; ++l) {
            while (r < n && cnt > 0) {
                update(word1[r] - 'a', 1);
                r++;
            }
            if(cnt == 0) {
                ans += n - r + 1;
            }
            update(word1[l] - 'a', -1);
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(|C|)$，$C$ 为字符集的大小，本题为 $26$