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

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

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

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

1 <= word1.length <= 1000000。

1 <= word2.length <= 10000。

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

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

输出：1。

解释：

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

题目来自leetcode3298。

详细步骤说明：1. 统计 word2 的字符需求• 创建一个长度为26的数组 diff，代表26个小写字母的计数差异。• 遍历 word2 中的每个字符，将对应位置的计数减1（即 diff[c - 'a']--），表示我们对这些字符的需求。• 例如 word2 是 "abc"，diff['a'-'a'] = -1，diff['b'-'a'] = -1，diff['c'-'a'] = -1，其余为0，表示这三个字符是必须出现的。2. 统计字符需求未满足的数量• 统计 diff 数组中小于0的元素个数，记为 cnt。• 这个 cnt 表示还有多少种字符的需求尚未被满足。• 开始时，cnt 就是 word2 有多少种不同字符，因为它们在 diff 中是负数。3. 采用滑动窗口遍历 word1，动态调整 diff 和 cnt• 设置两个指针，l（左边界）和 r（右边界），初始均指向字串起点。• 定义一个窗口即子字符串 word1[l:r]。• 通过移动指针，动态更新 diff 和 cnt 来判断当前窗口内字符是否满足条件。• 更新规则：• 当右指针 r 指向的字符加入窗口时，更新该字符计数在 diff 中增加1。• 若某字符的计数由负变零，说明该字符需求得到满足，cnt 减1。• 当左指针 l 移出一个字符时，把对应字符计数减少1。• 若某字符计数由零变负了，说明需求被破坏，cnt 增1。4. 通过移动右指针满足字符需求• 循环让右指针往右移动，直到 cnt 为0，说明当前窗口满足 word2 字符需求（即子串字符集包含 word2所有要求的字符数）。• 注意，右指针可能移动到子串末尾。5. 统计满足条件的子串数• 当 cnt 为0时：• 代表从当前位置 l 开始的子串，任意以 r 或更右边作为结束位置的子串，均满足条件。• 由于以 r 结尾的窗口是最小满足条件的窗口，从 r 到 word1 末尾，共有 len(word1) - r + 1 个子串以 l 为左边界满足条件。• 将这些子串数累加到结果 res 中。6. 左指针右移，继续查找其它满足条件的子串• 左指针右移一位，弹出最左字符，更新 diff 和 cnt，再重复上述过程。• 持续执行直到 l 指向 word1 结尾。总结

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

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

时间复杂度• 滑动窗口中左、右指针均在字符串上只移动一遍，整体指针移动次数不超过 O(len(word1))。• 更新 diff 和 cnt 的操作为常数时间。• 整体时间复杂度为 O(n)，n = word1 长度。空间复杂度• 需要一个固定长度为26的数组 diff，用于存储字符差异计数，无论输入多大，空间固定。• 额外空间约为 O(1)。结论

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

Go完整代码如下：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 {            cnt++        }    }    var res int64    l, r := 0, 0    for l < len(word1) {        for r < len(word1) && cnt > 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] * 26 for c in word2: diff[ord(c) - ord('a')] -= 1 cnt = sum(1for x in diff if x < 0) defupdate(diff, c, add): nonlocal cnt diff[c] += add if add == 1and diff[c] == 0: # diff[c] 从 -1 变成 0 cnt -= 1 elif add == -1and diff[c] == -1: # diff[c] 从 0 变成 -1 cnt += 1 res = 0 l = 0 r = 0 n = len(word1) while l < n: while r < n and cnt > 0: update(diff, ord(word1[r]) - ord('a'), 1) r += 1 if cnt == 0: # 符合条件的子字符串数量 res += n - r + 1 update(diff, ord(word1[l]) - ord('a'), -1) l += 1 return resif __name__ == "__main__": word1 = "bcca" word2 = "abc" result = valid_substring_count(word1, word2) print(result)

·

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展

·