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; } };
|