2025-04-27：统计重新排列后包含另一个字符串的子字符串数目Ⅱ

摘要：• 创建一个长度为26的数组 diff，代表26个小写字母的计数差异。• 遍历 word2 中的每个字符，将对应位置的计数减1（即 diff[c - 'a']--），表示我们对这些字符的需求。• 例如 word2 是 "abc"，diff['a'-'a'] =

2025-04-27：统计重新排列后包含另一个字符串的子字符串数目Ⅱ。用go语言，给定两个字符串 word1 和 word2，

如果存在一个字符串 x，将 x 重排后，word2 恰好是该重排字符串的前缀，我们就称这个字符串 x 是“合法的”。

现在需要计算在 word1 中，有多少个子字符串满足“合法”的条件。

此外，因为本题对内存使用有较严要求，解法必须保证时间复杂度为线性，即 O(n)。

word1 和 word2 都只包含小写英文字母。

输入：word1 = "bcca", word2 = "abc"。

输出：1。

解释：

唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

题目来自leetcode3298。

• 创建一个长度为26的数组 diff，代表26个小写字母的计数差异。• 遍历 word2 中的每个字符，将对应位置的计数减1（即 diff[c - 'a']--），表示我们对这些字符的需求。• 例如 word2 是 "abc"，diff['a'-'a'] = -1，diff['b'-'a'] = -1，diff['c'-'a'] = -1，其余为0，表示这三个字符是必须出现的。• 设置两个指针，l（左边界）和 r（右边界），初始均指向字串起点。• 定义一个窗口即子字符串 word1[l:r]。• 通过移动指针，动态更新 diff 和 cnt 来判断当前窗口内字符是否满足条件。• 更新规则：• 当右指针 r 指向的字符加入窗口时，更新该字符计数在 diff 中增加1。• 若某字符的计数由负变零，说明该字符需求得到满足，cnt 减1。• 当左指针 l 移出一个字符时，把对应字符计数减少1。• 若某字符计数由零变负了，说明需求被破坏，cnt 增1。

通过滑动窗口，维护 diff 和 cnt，实现以线性方式找到所有满足合法条件的子串。

代码中 update 函数负责维护 diff 和 cnt 的值，使得计算更加高效。

该方法在保证线性时间复杂度 O(n) 的基础上，实现了对字符需求的快速更新和判断，空间复杂度为常量级，符合题目对性能和内存限制的要求。

package mainimport ( "fmt")func validSubstringCount(word1 string, word2 string)int64 { diff := make(int, 26) for _, c := range word2 { diff[c-'a']-- } cnt := 0 for _, c := range diff { if c 0 { update(diff, int(word1[r]-'a'), 1, &cnt) r++ } if cnt == 0 { res += int64(len(word1) - r + 1) } update(diff, int(word1[l]-'a'), -1, &cnt) l++ } return res}func update(diff int, c, add int, cnt *int) { diff[c] += add if add == 1 && diff[c] == 0 { // 表明 diff[c] 由 -1 变为 0 *cnt-- } elseif add == -1 && diff[c] == -1 { // 表明 diff[c] 由 0 变为 -1 *cnt++ }}func main { word1 := "bcca" word2 := "abc" result := validSubstringCount(word1, word2) fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defvalid_substring_count(word1: str, word2: str) -> int:diff = [0] * 26for c in word2:diff[ord(c) - ord('a')] -= 1cnt = sum(1for x in diff if x 0:update(diff, ord(word1[r]) - ord('a'), 1)r += 1if cnt == 0:# 符合条件的子字符串数量res += n - r + 1update(diff, ord(word1[l]) - ord('a'), -1)l += 1return resif __name__ == "__main__":word1 = "bcca"word2 = "abc"result = valid_substring_count(word1, word2)print(result)