摘要：2025-05-16：字符至少出现 K 次的子字符串Ⅰ。用go语言，给定一个字符串 s 和一个整数 k，要求统计 s 中所有子字符串里，至少有某个字符出现的次数不少于 k 的子字符串数量。子字符串指的是 s 中连续且非空的一段字符。
2025-05-16：字符至少出现 K 次的子字符串Ⅰ。用go语言，给定一个字符串 s 和一个整数 k，要求统计 s 中所有子字符串里，至少有某个字符出现的次数不少于 k 的子字符串数量。子字符串指的是 s 中连续且非空的一段字符。
1
1
s 仅由小写英文字母组成。
输入： s = "abacb", k = 2。
输出： 4。
解释：
符合条件的子字符串如下：
"aba"（字符 'a' 出现 2 次）。
"abac"（字符 'a' 出现 2 次）。
"abacb"（字符 'a' 出现 2 次）。
"bacb"（字符 'b' 出现 2 次）。
题目来自leetcode3325。
1. 初始化：• 使用一个长度为 26 的数组 cnt 来记录当前窗口中每个字符的出现次数。• 使用 left 指针表示窗口的左边界，初始化为 0。• 初始化结果 ans 为 0。2. 滑动窗口：• 遍历字符串 s，每次处理一个字符 c：• 将 c 的出现次数 cnt[c-'a'] 加 1。• 检查当前字符 c 的出现次数是否 ≥ k：• 如果是，说明当前窗口（从 left 到当前字符）可能包含满足条件的子字符串。• 我们需要移动 left 指针，直到 c 的出现次数 • 每次移动 left 时，将 s[left] 的出现次数减 1，并将 left 右移。• 这样做的目的是确保窗口内至少有一个字符的出现次数 ≥ k。• 将 left 的值加到 ans 中：• 因为从 left 到当前字符的所有子字符串都满足条件（至少有一个字符的出现次数 ≥ k）。• 例如，当前窗口是 [left, right]，那么以 right 结尾的子字符串中，[left, right]、[left+1, right]、...、[right, right] 都满足条件，共有 left 个。3. 返回结果：• 最终 ans 就是所有满足条件的子字符串数量。package mainimport ( "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] * 26left = 0ans = 0for c in s:cnt[ord(c) - ord('a')] += 1while cnt[ord(c) - ord('a')] >= k:cnt[ord(s[left]) - ord('a')] -= 1left += 1ans += leftreturn anss = "abacb"k = 2result = numberOfSubstrings(s, k)print(result)我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
·
来源：真来教育