创建个人网站教案_微信公众号开店流程_如何推广网站_2023年5月最新疫情

问题背景

给你两个字符串 $wor{d}_1$ 和 $wor{d}_2$。
如果一个字符串 $x$ 重新排列后，$wor{d}_2$ 是重排字符串的 前缀，那么我们称字符串 $x$ 是 合法的。
请你返回 $wor{d}_1$ 中 合法 子字符串 的数目。

数据约束

• $1\le wor{d}_1.length\le 10^5$
• $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;}
}