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. 1. 初始化差异计数数组（diff）
2. • 创建一个长度为26的整型数组 diff，对应26个小写字母。
3. • 对于 word2 中每个字符，将对应字母在 diff 中的计数减1。
   这样 diff 中的每个位置表示对应字母在目标字符串 word2 中的缺失数量（负数表示比 word2 中出现多的字母数量，正数则表示还缺字符）。
4. 2. 统计初始缺失计数（cnt）
5. • cnt 表示当前还“缺”多少种字母满足 word2 的要求（即 diff 中出现负数的字母种类数）。
6. • 通过扫描 diff 数组，统计小于0的元素个数，赋值给 cnt。
7. 3. 使用双指针扫描 word1 子字符串
8. • 用两个指针 l 和 r 分别表示子串的左右边界，初始都指向字符串开始。
9. • 目的：通过不断移动指针，在 word1 上找到所有满足“合法”条件的子串。
10. 4. 右指针移动，补充字母，缩小缺失计数
11. • 当 cnt > 0 说明当前子串不能覆盖 word2 所有字母的要求，说明存在缺字符。
12. • 移动右指针 r 右移一个字符，将其对应字母计数在 diff 中增加1。
13. • 通过 update 函数更新 diff，若某个字母从缺失变为满足，cnt 减1。
14. • 如此，右边扩展区间，直到 cnt == 0，即当前区间已经满足 word2 的字母需求。
15. 5. 计算合法子串个数
16. • 当 cnt == 0 时，说明当前下标区间 [l, r) 对应的子串可以重排列后使 word2 成为其前缀。
17. • 此时，所有以 l 开头，且右端点在 r 到 len(word1) 之间的子串都是合法的（因为再扩展右边界没有减少字母数量）。
18. • 因此，合法子串数增加 len(word1) - r + 1。
19. 6. 左指针右移，增加缺失计数
20. • 移动左指针 l，从子串中移除最左边字符，将它对应字母计数在 diff 中减1。
21. • 通过 update 函数更新 cnt，如果某个字母由满足到缺失，cnt 增加1。
22. • 重复右指针扩展过程，继续寻找下一个满足条件的区间。
23. 7. 循环终止
24. • 当 l 移动到字符串末尾时，结束循环。
25. • 累计计算出的合法子串数即为最终结果返回。

总结核心思路

• • 使用 差异计数数组 diff 来动态记录当前子串的字母与目标字符串 word2 的差异。
• • 以 双指针滑动窗口 方式在 word1 中找到所有包含 word2 字母的子串，满足所有字母的数量都不少于 word2 中的数量。
• • 通过 cnt 变量快速判断当前窗口是否满足条件，避免每次都全量判断。
• • 根据当前窗口满足条件时，计算以左指针为起点，右指针及之后的所有子串数量。

时间复杂度分析

• • 双指针遍历 word1，左指针和右指针各最多遍历一遍字符串，总体操作基本是线性。
• • 每次移动指针，调用 update 函数，操作数组 diff 常数时间内完成。
  因此，总体时间复杂度： O(n)，n = word1 的长度。

空间复杂度分析

• • 维护一个长度为26的整型数组 diff，固定大小，空间开销为 O(1)。
• • 其他变量使用常数空间。
• • 不需要额外开辟与字符串长度相关的存储空间。

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

结论

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

Go完整代码如下：

package main

import (
    "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 main

import (
    "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 语言和算法助力您的职业发展

·