3297. 统计重新排列后包含另一个字符串的子字符串数目 I

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 

前缀，那么我们称字符串 x 是 合法的 。

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

思路

一开始用的是前缀和思想，但是超时，不过749 / 758 个通过的测试用例，觉得可惜，也把代码复制过来，第一次写二维前缀和，就写对了。

不超时的思路是滑动窗口，窗口里始终保持着不完全包含word2，当word2的所有字母被包含（即表的所有值都不大于0）时开始滑左边、直到窗口中的串不再包含word2 。每次滑动后窗口时，意味着里面是包含word2的，这时需要更新ans值。

代码

二维前缀和（超时）：

class Solution {
    public long validSubstringCount(String word1, String word2) {
        long ans=0;
        int len=word1.length();
        long[][] preSum = new long[len+1][26];
        preSum[1][word1.charAt(0)-'a'] = 1;
        for (int i=2; i<=len; i++) {
            for (int j=0; j<26; j++) {
                preSum[i][j] = preSum[i-1][j];
            }
            preSum[i][word1.charAt(i-1)-'a']++;
        }
        long[] sum = new long[26];
        for (int i=0; i<word2.length(); i++) {
            sum[word2.charAt(i)-'a']++;
        }

        for (int i=0; i<=len; i++) {
            for (int j=i; j<=len; j++) {
                boolean flag=true;
                for (int k=0; k<26; k++) {
                    if (preSum[j][k]-preSum[i][k] < sum[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans++;
            }
        }
        return ans;
    }
}

滑动窗口：

class Solution {
    public long validSubstringCount(String word1, String word2) {
        long ans=0L;
        int len = word1.length();
        int[] sum = new int[26];
        for (int i=0; i<word2.length(); i++) {
            sum[word2.charAt(i)-'a']++;
        }
        int tail=0, head=0;
        while (head < len) {
            sum[word1.charAt(head)-'a']--;

            while(tail <= head && isValid(sum)) {
                ans += len - head;  //核心代码
                sum[word1.charAt(tail)-'a']++;
                tail++;
            }
            
            head++;
        }
        return ans;
    }

    public boolean isValid(int[] sum) {
        for (int num : sum) {
            if (num > 0 )return false;
        }
        return true;
    }
}