给你两个字符串 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 <= 10^51 <= word2.length <= 10^4word1和word2都只包含小写英文字母。
分析：先统计word2中出现了哪些字母以及对应字母出现了多少次。然后遍历word1，同样记录每个字符出现的次数。当当前的字符是word2出现的字符时，要比较是否次数超过了word2，如果超过了，是否word2中所有的字符都已经出现了足够多的次数。
我们用哈希表维护当前窗口内每种字符的出现次数，初始时窗口长度为 0，每次我们向右移动 r，并将字符加入哈希表，直到每种字符的出现次数都大于 word2 中的出现次数，此时将答案累加 n−r+1。接着我们要计算 l+1 作为左边界的情况，将 l 处的字符移除哈希表，并继续向右移动 r，重复前面的过程即可。
long long validSubstringCount(char* word1, char* word2) {long long ans=0;int l1=strlen(word1),l2=strlen(word2);int flag1[30]={0},flag2[30]={0},cnt=0;//flag1标记word1，flag2标记word2，cnt表示word1已经满足了多少个word2的字符for(int i=0;i<l2;++i){int t=word2[i]-'a';flag2[t]++;if(flag2[t]==1)cnt++;}int f=0,l=0;for(int i=0;i<l1;++i){int t=word1[i]-'a';flag1[t]++;if(flag1[t]==flag2[t])f++;if(f==cnt){printf("i=%d l1=%d\n",i,l1);ans+=l1-i;int index=word1[l]-'a';flag1[index]--;if(flag1[index]<flag2[index]&&flag2[index]!=0)f--;l++;if(flag1[t]==flag2[t])f--;flag1[t]--;i--;}}return ans;
}
