class Solution {
public:
int numberOfSubstrings(string s, int k) {
}
};
3325. 字符至少出现 K 次的子字符串 I
给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。
子字符串 是字符串中的一个连续、 非空 的字符序列。
示例 1：
输入： s = "abacb", k = 2
输出： 4
解释：
符合条件的子字符串如下：
"aba"（字符 'a' 出现 2 次）。"abac"（字符 'a' 出现 2 次）。"abacb"（字符 'a' 出现 2 次）。"bacb"（字符 'b' 出现 2 次）。示例 2：
输入： s = "abcde", k = 1
输出： 15
解释：
所有子字符串都有效，因为每个字符至少出现一次。
提示：
1 <= s.length <= 30001 <= k <= s.lengths 仅由小写英文字母组成。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4 MB, 提交时间: 2024-10-23 09:31:59
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
}
python3 解法, 执行用时: 5 ms, 内存消耗: 16.5 MB, 提交时间: 2024-10-23 09:31:46
class Solution:
def numberOfSubstrings(self, s: str, k: int) -> int:
ans = left = 0
cnt = defaultdict(int)
for c in s:
cnt[c] += 1
while cnt[c] >= k:
cnt[s[left]] -= 1
left += 1
ans += left
return ans
java 解法, 执行用时: 1 ms, 内存消耗: 41.5 MB, 提交时间: 2024-10-23 09:31:12
class Solution {
int numberOfSubstrings(String S, int k) {
char[] s = S.toCharArray();
int ans = 0;
int left = 0;
int[] cnt = new int[26];
for (char c : s) {
cnt[c - 'a']++;
while (cnt[c - 'a'] >= k) {
cnt[s[left] - 'a']--;
left++;
}
ans += left;
}
return ans;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 8.7 MB, 提交时间: 2024-10-23 09:30:59
// 滑动窗口
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int ans = 0, left = 0, cnt[26]{};
for (char c : s) {
cnt[c - 'a']++;
while (cnt[c - 'a'] >= k) {
cnt[s[left] - 'a']--;
left++;
}
ans += left;
}
return ans;
}
};