【LeetCode】每日一题 2024_1_10 统计重新排列后包含另一个字符串的子字符串数目 II（滑动窗口）

ops/2025/1/12 23:25:46/

前言

每天和你一起刷 LeetCode 每日一题~

拼尽全力无法战胜期末考试

寒假 . . . 堂堂复活！

每日一题重出江湖！

就用我最擅长的滑动窗口类型的每日一题作为我寒假回归的第一题！

LeetCode 启动！

题目：leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/description/?envType=daily-question&envId=2025-01-10" rel="nofollow">统计重新排列后包含另一个字符串的子字符串数目 II

代码与解题思路

先读题：用 word2 作为 word1 子串重排之后的前缀就算作一个合法字符串，问总共有多少个合法字符串

对于这个题目，我们需要理解的核心问题就是：

判断字符串是否合法，因为 word1 字符串可以重排，所以判断 word2 是否能成为 word1 的前缀，就需要对每个字符进行计数并判断 word1 子串字符的计数是否大于等于 word2 子串的数量

代码及详细注释如下：

func validSubstringCount(word1 string, word2 string) (ans int64) {// 经典子数组型滑窗// word2 作为 word1 的前缀，将他的字符计数需要在 word1 子串中全部出现need := [26]int{} // 记录 word1 子串出现的字符cnt := [26]int{}// 用于判断 word2 和 word1 字符计数相同//（不能用 map 判断，因为会出现 word1 字符比 word2 多但是符合条件的情况）// 字符的种类typeCnt := 0for _, v := range word2 {idx := int(v-'a')if need[idx] == 0 { // 字符种类++typeCnt++}need[idx]++}// 滑窗l := 0for r, v := range word1 {idx := int(v-'a')cnt[idx]++// word1 当前字符数量 >= word2 时，word2 都能作为 word1 的前缀if cnt[idx] == need[idx] {typeCnt--}// 当 word2 中字符都在 word1 子串出现了，证明可以作为他的前缀了for typeCnt == 0 {// 枚举左边界// 即当前子串已经符合要求，右边界无论加多少字符依然符合，所以直接把右边界都加上ans += int64(len(word1)-r) ldx := int(word1[l]-'a') // 左边界出窗口cnt[ldx]--// word1 当前字符数量 < word2，word2 不能作为 word1 的前缀if cnt[ldx] < need[ldx] {typeCnt++}l++}}return ans
}