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

方法一：滑动窗口
题目实际上是求在 word1 中，有多少个子串包含了 word2 中的所有字符。我们可以使用滑动窗口来处理。

首先，如果 word1 的长度小于 word2 的长度，那么 word1 中不可能包含 word2 的所有字符，直接返回 0。

接下来，我们用一个哈希表或长度为 26 的数组 cnt 来统计 word2 中的字符出现的次数。然后，我们用 need 来记录还需要多少个字符才能满足条件，初始化为 cnt 的长度。

接着，我们用一个滑动窗口 win 来记录当前窗口中的字符出现的次数。我们用 ans 来记录满足条件的子串的个数，用 l 来记录窗口的左边界。

遍历 word1 中的每个字符，对于当前字符 c，我们将其加入到 win 中，如果 win[c] 的值等于 cnt[c]，那么说明当前窗口中已经包含了 word2 中的所有字符之一，那么 need 减一。如果 need 等于 0，说明当前窗口中包含了 word2 中的所有字符，我们需要缩小窗口的左边界，直到 need 大于 0。具体地，如果 win[word1[l]] 等于 cnt[word1[l]]，那么说明当前窗口中包含了 word2 中的所有字符之一，那么缩小窗口的左边界之后，就不满足条件了，所以 need 加一，同时 win[word1[l]] 减一。然后，我们将 l 加一。此时窗口为 [l,r]，那么对于任意 0≤l
′
<l，[l
′
,r] 都是满足条件的子串，一共有 l 个，我们累加到答案中。

public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return 0;
        }
        int[] cnt = new int[26];
        int need = 0;
        for (int i = 0; i < word2.length(); ++i) {
            if (++cnt[word2.charAt(i) - 'a'] == 1) {
                ++need;
            }
        }
        long ans = 0;
        int[] win = new int[26];
        for (int l = 0, r = 0; r < word1.length(); ++r) {
            int c = word1.charAt(r) - 'a';
            if (++win[c] == cnt[c]) {
                --need;
            }
            while (need == 0) {
                c = word1.charAt(l) - 'a';
                if (win[c] == cnt[c]) {
                    ++need;
                }
                --win[c];
                ++l;
            }
            ans += l;
        }
        return ans;
    }