技术开发包括软件开发吗_房地产市场信息系统网站_google推广怎么做_互联网营销师培训大纲

给你两个字符串 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^6
• 1 <= word2.length <= 10^4
• word1 和 word2 都只包含小写英文字母。

分析：和3297类似的解法，使用滑动窗口计算。先用一个大小为26的数组，记录word2中各个字母出现的次数。之后遍历word1数组，初始时，左端点left为0。遍历时，用另一个大小为26的数组记录word1中各个字母出现的次数。

如何知道从left到当前遍历位置出现的字符已经可以构成word2呢？初始时没有一个字符能满足数量，记录满足数量f=0，而所有word2出现过的不同字符数记为cnt，每次word1的字符数+1时若满足word2中对应字符的数量，则f++，当f等于cnt时，说明从left到当前位置已经满足条件了。

此时开始向右移动left，并把left对应的字符数量减1，再判断f与cnt是否相等。这样一直把word1遍历完即可。

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;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){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;
}