comments | difficulty | edit_url | tags | |||
---|---|---|---|---|---|---|
true |
Hard |
|
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.
Example 1:
Input: s = "abacb", k = 2
Output: 4
Explanation:
The valid substrings are:
- "
aba"
(character'a'
appears 2 times). "abac"
(character'a'
appears 2 times)."abacb"
(character'a'
appears 2 times)."bacb"
(character'b'
appears 2 times).
Example 2:
Input: s = "abcde", k = 1
Output: 15
Explanation:
All substrings are valid because every character appears at least once.
Constraints:
1 <= s.length <= 3 * 105
1 <= k <= s.length
s
consists only of lowercase English letters.
We can enumerate the right endpoint of the substring, and then use a sliding window to maintain the left endpoint of the substring, ensuring that the occurrence count of each character in the sliding window is less than
We can use an array
When we enumerate the right endpoint, we can add the character at the right endpoint to the sliding window, then check if the occurrence count of the character at the right endpoint in the sliding window is greater than or equal to
After enumeration, we return the answer.
The time complexity is
class Solution:
def numberOfSubstrings(self, s: str, k: int) -> int:
cnt = Counter()
ans = l = 0
for c in s:
cnt[c] += 1
while cnt[c] >= k:
cnt[s[l]] -= 1
l += 1
ans += l
return ans
class Solution {
public long numberOfSubstrings(String s, int k) {
int[] cnt = new int[26];
long ans = 0;
for (int l = 0, r = 0; r < s.length(); ++r) {
int c = s.charAt(r) - 'a';
++cnt[c];
while (cnt[c] >= k) {
--cnt[s.charAt(l) - 'a'];
l++;
}
ans += l;
}
return ans;
}
}
class Solution {
public:
long long numberOfSubstrings(string s, int k) {
int n = s.size();
long long ans = 0, l = 0;
int cnt[26]{};
for (char& c : s) {
++cnt[c - 'a'];
while (cnt[c - 'a'] >= k) {
--cnt[s[l++] - 'a'];
}
ans += l;
}
return ans;
}
};
func numberOfSubstrings(s string, k int) (ans int64) {
l := 0
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
for cnt[c-'a'] >= k {
cnt[s[l]-'a']--
l++
}
ans += int64(l)
}
return
}
function numberOfSubstrings(s: string, k: number): number {
let [ans, l] = [0, 0];
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
const x = c.charCodeAt(0) - 97;
++cnt[x];
while (cnt[x] >= k) {
--cnt[s[l++].charCodeAt(0) - 97];
}
ans += l;
}
return ans;
}