2025-04-26：统计重新排列后包含另一个字符串的子字符串数目Ⅰ。用go语言，给定两个字符串 word1 和 word2。如果存在一个字符串 x，使得经过重新排列后，word2 是 x 的一个前缀，那么 x 就被称为“合法”的字符串。

请你计算并返回 word1 中所有满足“合法”条件的子字符串的数量。

1 <= word1.length <= 100000。

1 <= word2.length <= 10000。

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

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

输出：1。

解释：

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

题目来自leetcode3297。

算法大体流程分步骤：1. 初始化差异计数数组（diff）• 创建一个长度为26的整型数组 diff，对应26个小写字母。• 对于 word2 中每个字符，将对应字母在 diff 中的计数减1。这样 diff 中的每个位置表示对应字母在目标字符串 word2 中的缺失数量（负数表示比 word2 中出现多的字母数量，正数则表示还缺字符）。2. 统计初始缺失计数（cnt）• cnt 表示当前还“缺”多少种字母满足 word2 的要求（即 diff 中出现负数的字母种类数）。• 通过扫描 diff 数组，统计小于0的元素个数，赋值给 cnt。3. 使用双指针扫描 word1 子字符串• 用两个指针 l 和 r 分别表示子串的左右边界，初始都指向字符串开始。• 目的：通过不断移动指针，在 word1 上找到所有满足“合法”条件的子串。4. 右指针移动，补充字母，缩小缺失计数• 当 cnt > 0 说明当前子串不能覆盖 word2 所有字母的要求，说明存在缺字符。• 移动右指针 r 右移一个字符，将其对应字母计数在 diff 中增加1。• 通过 update 函数更新 diff，若某个字母从缺失变为满足，cnt 减1。• 如此，右边扩展区间，直到 cnt == 0，即当前区间已经满足 word2 的字母需求。5. 计算合法子串个数• 当 cnt == 0 时，说明当前下标区间 [l, r) 对应的子串可以重排列后使 word2 成为其前缀。• 此时，所有以 l 开头，且右端点在 r 到 len(word1) 之间的子串都是合法的（因为再扩展右边界没有减少字母数量）。• 因此，合法子串数增加 len(word1) - r + 1。6. 左指针右移，增加缺失计数• 移动左指针 l，从子串中移除最左边字符，将它对应字母计数在 diff 中减1。• 通过 update 函数更新 cnt，如果某个字母由满足到缺失，cnt 增加1。• 重复右指针扩展过程，继续寻找下一个满足条件的区间。7. 循环终止• 当 l 移动到字符串末尾时，结束循环。• 累计计算出的合法子串数即为最终结果返回。总结核心思路• 使用 差异计数数组 diff 来动态记录当前子串的字母与目标字符串 word2 的差异。• 以 双指针滑动窗口 方式在 word1 中找到所有包含 word2 字母的子串，满足所有字母的数量都不少于 word2 中的数量。• 通过 cnt 变量快速判断当前窗口是否满足条件，避免每次都全量判断。• 根据当前窗口满足条件时，计算以左指针为起点，右指针及之后的所有子串数量。时间复杂度分析• 双指针遍历 word1，左指针和右指针各最多遍历一遍字符串，总体操作基本是线性。• 每次移动指针，调用 update 函数，操作数组 diff 常数时间内完成。因此，总体时间复杂度： O(n)，n = word1 的长度。空间复杂度分析• 维护一个长度为26的整型数组 diff，固定大小，空间开销为 O(1)。• 其他变量使用常数空间。• 不需要额外开辟与字符串长度相关的存储空间。

因此，总体额外空间复杂度： O(1)。

结论

该算法通过差异数组和双指针滑动窗口，线性高效地统计满足条件的合法子串数，额外空间开销固定，适合处理长度较大的字符串。

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完整代码如下：

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)}

·

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

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

·