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

福大大架构师每日一题

发布于 2025-04-26 21:29:13

18100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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

# -*-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)

    res = 0
    l, r = 0, 0
    n = len(word1)

    defupdate(diff, c, add, cnt_ref):
        diff[c] += add
        if add == 1and diff[c] == 0:
            cnt_ref[0] -= 1
        elif add == -1and diff[c] == -1:
            cnt_ref[0] += 1

    cnt_ref = [cnt]

    while l < n:
        while r < n and cnt_ref[0] > 0:
            update(diff, ord(word1[r]) - ord('a'), 1, cnt_ref)
            r += 1
        if cnt_ref[0] == 0:
            res += n - r + 1
        update(diff, ord(word1[l]) - ord('a'), -1, cnt_ref)
        l += 1

    return res


if __name__ == '__main__':
    word1 = "bcca"
    word2 = "abc"
    result = valid_substring_count(word1, word2)
    print(result)