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

给你两个字符串 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;
}

原文地址：https://blog.csdn.net/2401_88085478/article/details/145055117

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！