题目：
给你两个字符串 word1 和 word2 。如果一个字符串 x 重新排列后，word2 是重排字符串的前缀
，那么我们称字符串 x 是 合法的 。请你返回 word1 中 合法 子字符串的数目。
注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。
示例 1：
输入：word1 = “bcca”, word2 = “abc”
输出：1
解释：唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。
示例 2：
输入：word1 = “abcabc”, word2 = “abc”
输出：10
解释：除了长度为 1 和 2 的所有子字符串都是合法的。
示例 3：
输入：word1 = “abcabc”, word2 = “aaabc”
输出：0
解释：
1 <= word1.length <= 1061 <= word2.length <= 104word1和word2都只包含小写英文字母。
思路：
我们的目标是求解 word1 中有多少子串经过重新排列后存在一个前缀是 word2，也就是说要求解有多少子串包含 word2 中的全部字符。
对于每个 l(0≤l<n)，找到最小的 r(l≤r<n)，使得 word1 区间 [l,r] 内包含 word2 的全部字符，可以发现子串 [l,r+1],[l,r+2],⋯,[l,n] 都是满足要求的，计数 n−r+1 。将所有的计数都加起来就是答案。
注意到每次找到 l 匹配的 r 后，将 l 增加 1，区间内的字符减少，相应的 r 势必会增加。因此得到结论：随着 l 的增加，r 也会增加，我们可以使用滑动窗口来求解。
具体来说，我们用哈希表维护当前窗口内每种字符的出现次数，初始时窗口长度为 0，每次我们向右移动 r，并将字符加入哈希表，直到每种字符的出现次数都大于 word2 中的出现次数，此时将答案累加 n−r+1。接着我们要计算 l+1 作为左边界的情况，将 l 处的字符移除哈希表，并继续向右移动 r，重复前面的过程即可。
我们在上面采用了 O(C) 的时间复杂度判断滑动窗口内每种字符的出现次数是否都大于 word2 中的出现次数，其实还可以进一步优化。我们将维护的对象更改为滑动窗口内每种字符出现次数与 word2 中每种字符出现次数的差值，当所有差值都大于等于 0 则表示合法。但到这一步还没有与之前的方法拉开差距，需要再维护一个变量 cnt 表示差值小于 0 的字符种类数，当 cnt 等于 0 则表示合法。在滑动窗口移动时，可以仅消耗 O(1) 的时间来维护 cnt，这样一来就降低了时间复杂度。
代码：
class Solution {
public:
long long validSubstringCount(string word1, string word2) {
vector<int> diff(26, 0);
for (auto c : word2) {
diff[c - 'a']--;
}
long long res = 0;
int cnt = count_if(diff.begin(), diff.end(), [](int c) { return c < 0; });
auto update = [&](int c, int add) {
diff[c] += add;
if (add == 1 && diff[c] == 0) {
// 表明 diff[c] 由 -1 变为 0
cnt--;
} else if (add == -1 && diff[c] == -1) {
// 表明 diff[c] 由 0 变为 -1
cnt++;
}
};
for (int l = 0, r = 0; l < word1.size(); l++) {
while (r < word1.size() && cnt > 0) {
update(word1[r] - 'a', 1);
r++;
}
if (cnt == 0) {
res += word1.size() - r + 1;
}
update(word1[l] - 'a', -1);
}
return res;
}
};