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.
c++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;
}
};
|
