2025-05-16：字符至少出现 K 次的子字符串Ⅰ。用go语言，给定一个字符串 s 和一个整数 k，要求统计 s 中所有子字符串里，至少有某个字符出现的次数不少于 k 的子字符串数量。子字符串指的是 s 中连续且非空的一段字符。

1 <= s.length <= 3000。

1 <= k <= s.length。

s 仅由小写英文字母组成。

输入： s = "abacb", k = 2。

输出： 4。

解释：

符合条件的子字符串如下：

"aba"（字符 'a' 出现 2 次）。

"abac"（字符 'a' 出现 2 次）。

"abacb"（字符 'a' 出现 2 次）。

"bacb"（字符 'b' 出现 2 次）。

题目来自leetcode3325。

具体步骤

1. 1. 初始化：
2. o 使用一个长度为 26 的数组 cnt 来记录当前窗口中每个字符的出现次数。
3. o 使用 left 指针表示窗口的左边界，初始化为 0。
4. o 初始化结果 ans 为 0。
5. 2. 滑动窗口：
6. o 遍历字符串 s，每次处理一个字符 c：
7. o 将 c 的出现次数 cnt[c-'a'] 加 1。
8. o 检查当前字符 c 的出现次数是否 ≥ k：
9. o 如果是，说明当前窗口（从 left 到当前字符）可能包含满足条件的子字符串。
10. o 我们需要移动 left 指针，直到 c 的出现次数 < k：
11. o 每次移动 left 时，将 s[left] 的出现次数减 1，并将 left 右移。
12. o 这样做的目的是确保窗口内至少有一个字符的出现次数 ≥ k。
13. o 将 left 的值加到 ans 中：
14. o 因为从 left 到当前字符的所有子字符串都满足条件（至少有一个字符的出现次数 ≥ k）。
15. o 例如，当前窗口是 [left, right]，那么以 right 结尾的子字符串中，[left, right]、[left+1, right]、...、[right, right] 都满足条件，共有 left 个。
16. 3. 返回结果：
17. o 最终 ans 就是所有满足条件的子字符串数量。

时间复杂度和空间复杂度

• o 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被处理两次（一次被加入窗口，一次被移出窗口）。
• o 空间复杂度：O(1)，因为 cnt 数组的大小固定为 26（小写字母）。

Go完整代码如下：

package main

import (
    "fmt"
)

func numberOfSubstrings(s string, k int) (ans int) {
    cnt := [26]int{}
    left := 0
    for _, c := range s {
        cnt[c-'a']++
        for cnt[c-'a'] >= k {
            cnt[s[left]-'a']--
            left++
        }
        ans += left
    }
    return
}

func main() {
    s := "abacb"
    k := 2
    result := numberOfSubstrings(s, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defnumberOfSubstrings(s: str, k: int) -> int:
    cnt = [0] * 26
    left = 0
    ans = 0
    for c in s:
        cnt[ord(c) - ord('a')] += 1
        while cnt[ord(c) - ord('a')] >= k:
            cnt[ord(s[left]) - ord('a')] -= 1
            left += 1
        ans += left
    return ans

s = "abacb"
k = 2
result = numberOfSubstrings(s, k)
print(result)

·

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

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

·