[LeetCode] Count Substrings With K-Frequency Characters I

3325. Count Substrings With K-Frequency Characters I

Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times.

A substring is a contiguous non-empty sequence of characters within a string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int res = 0, prv = -1;
vector<int> cnt(26);
for(int l = 0, r = 0; r < s.length(); r++) {
if(++cnt[s[r]-'a'] == k) {
while(s[l] != s[r]) --cnt[s[l++]-'a'];
res += (l - prv) * (s.length() - r);
prv = l;
while(cnt[s[r]-'a'] == k) --cnt[s[l++]-'a'];
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/10/20/PS/LeetCode/count-substrings-with-k-frequency-characters-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.