2025-05-16：字符至少出现 K 次的子字符串Ⅰ。用go语言，给定一个字符串 s 和一个整数 k，要求统计 s 中所有子字

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

时间复杂度和空间复杂度

• • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被处理两次（一次被加入窗口，一次被移出窗口）。
• • 空间复杂度：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)