问题背景

给你两个字符串 $wor{d}_1$ 和 $wor{d}_2$。
如果一个字符串 $x$ 重新排列后，$wor{d}_2$ 是重排字符串的 前缀，那么我们称字符串 $x$ 是 合法的。
请你返回 $wor{d}_1$ 中 合法 子字符串 的数目。
注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。

数据约束

• $1\le wor{d}_1.length\le 10^6$
• $1\le wor{d}_2.length\le 10^4$
• $wor{d}_1$和$wor{d}_2$都只包含小写英文字母

解题过程

这题的关键在于能不能看出来实际上是在问 最小覆盖字串 的数量，如果能够意识到这一点，那就是一个标准的滑窗求符合要求的答案数量的题。

具体实现

class Solution {public long validSubstringCount(String word1, String word2) {char[] chW = word1.toCharArray();int n = chW.length;int[] diff = new int[26];int diffCount = 0;for(char c : word2.toCharArray()) {if(diff[c - 'a']++ == 0) {diffCount++;}}long res = 0;for(int left = 0, right = 0; right < n; right++) {if(--diff[chW[right] - 'a'] == 0) {diffCount--;}while(diffCount == 0) {res += n - right;if(diff[chW[left++] - 'a']++ == 0) {diffCount++;}}}return res;}
}