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

福大大架构师每日一题

发布于 2025-04-27 13:51:14

11000

代码可运行

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

运行总次数：0

代码可运行

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

    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 res

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