题目描述

给你两个字符串 word1 和 word2。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的。

请你返回 word1 中 合法 子字符串 的数目。

样例

输入：word1 = "bcca", word2 = "abc"

输出：1

解释：

唯一合法的子字符串是 "bcca"，可以重新排列得到 "abcc"，"abc" 是它的前缀。

输入：word1 = "abcabc", word2 = "abc"

输出：10

解释：

除了长度为 1 和 2 的所有子字符串都是合法的。

输入：word1 = "abcabc", word2 = "aaabc"

输出：0

限制

• 1 <= word1.length <= 10^5
• 1 <= word2.length <= 10^4
• word1 和 word2 都只包含小写英文字母。

算法

(双指针) $O(n + m + |\Sigma|)$

1. 对于每个区间右端点 $i$，都找到尽可能大的位置 $j$，满足区间集 $[0, i], [1, i], \dots, [j - 1, i]$ 都是满足条件的区间。
2. 注意到，$j$ 是随着 $i$ 增大而不减的，故可以使用双指针。
3. 判定区间是否满足条件可以通过比较区间内各个字母的出现次数，初始化计数器为在 word2 中没有出现过的字母个数。
4. 在移动 $i$ 的过程中，如果发现字母的出现次数恰好等于 word2 中对应字母的出现次数，则计数器增加 $1$。
5. 如果计数器达到了 $|\Sigma|$，则可以不断移动 $j$。在移动 $j$ 的过程中，如果发现字母的出现次数小于 word2 中对应字母的出现次数，则计数器减少 $1$。

时间复杂度

• 预处理的时间复杂度为 $O(m + |Sigma|)$。
• 移动双指针判断的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n + m + |\Sigma|)$。

空间复杂度

• 仅需要 $O(|Sigma|)$ 的额外空间存储字母的出现次数。

C++ 代码

#define LL long long

class Solution {
public:
    LL validSubstringCount(string word1, string word2) {
        const int S = 26;
        vector<int> target(S, 0);

        for (char c : word2)
            ++target[c - 'a'];

        int tot = 0;
        for (int i = 0; i < S; i++)
            if (target[i] == 0)
                ++tot;

        const int n = word1.size();
        vector<int> cnt(S, 0);
        LL ans = 0;

        for (int i = 0, j = 0; i < n; i++) {
            int c = word1[i] - 'a';

            ++cnt[c];
            if (cnt[c] == target[c])
                ++tot;

            while (tot == S) {
                c = word1[j] - 'a';

                --cnt[c];
                if (cnt[c] < target[c])
                    --tot;

                ++j;
            }

            ans += j;
        }

        return ans;
    }
};