Count Substrings With K-Frequency Characters I — Solution
Count Substrings With K-Frequency Characters I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Substrings With K-Frequency Characters I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s of lowercase English letters and an integer k, return the number of substrings of s in which at least one character appears at least k times.
Substrings at different positions count separately even when their text is equal.
Example 1
Input: s = "aabab", k = 2
Output: 7
Explanation: `"aa"`, `"aab"`, `"aaba"`, `"aabab"`, `"aba"`, `"abab"` and `"bab"`.
Example 2
Input: s = "codekairo", k = 1
Output: 45
Explanation: With `k = 1` every one of the 45 substrings qualifies.
Example 3
Input: s = "abcabc", k = 3
Output: 0
Explanation: No letter occurs three times.
Constraints
1 <= s.length <= 30001 <= k <= s.lengths consists only of lowercase English letters.
Hints for Count Substrings With K-Frequency Characters I
Hint 1
If a substring qualifies, extending it on either side keeps it qualifying.
Hint 2
For each end
right, the qualifying substrings ending there are exactly those starting before some positionleft— find that boundary.Hint 3
Slide a window that never qualifies: after adding
s[right], only that letter can have reachedk, so remove letters from the left while its count is at leastk. Then the starts0 .. left-1all qualify; addleft.
How to solve Count Substrings With K-Frequency Characters I
Keep the window [left, right] as the longest window ending at right in which every letter appears fewer than k times. Every start to the left of it gives a qualifying substring.
Approach
- Keep letter counts for the window,
left = 0andans = 0. - For each
right, increment the count ofc = s[right]. - While
count[c] >= k, decrement the count ofs[left]and advanceleft. - Add
lefttoans: the substringss[0..right], …,s[left-1..right]all contain some letterktimes.
Why it works
Before s[right] is added the window has all counts below k, so after adding it only c can reach k; shrinking until c drops below k restores the invariant with the smallest possible movement. At that moment s[left-1..right] had c exactly k times, so it — and every substring starting further left — qualifies, while s[left..right] does not. Since qualifying is preserved by extension, left never moves back, giving O(n) total.
Complexity
- Time —
O(n) - Space —
O(26)
Pitfalls
- Add
left, notright - left + 1: the window itself is the non-qualifying part. - Only the newly added letter can cross the threshold, so the shrink loop checks that one letter, not all 26.
- With
k = 1every substring qualifies — the answer isn(n+1)/2.
Reference solution
Python
def numberOfSubstrings(s: str, k: int) -> int:
cnt = [0] * 26
left = 0
ans = 0
for ch in s:
c = ord(ch) - 97
cnt[c] += 1
while cnt[c] >= k:
cnt[ord(s[left]) - 97] -= 1
left += 1
ans += left
return ansJava
public static int numberOfSubstrings(String s, int k) {
int[] cnt = new int[26];
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
int c = s.charAt(right) - 'a';
cnt[c]++;
while (cnt[c] >= k) {
cnt[s.charAt(left) - 'a']--;
left++;
}
ans += left;
}
return ans;
}C++
int numberOfSubstrings(string s, int k) {
int cnt[26] = {0};
int left = 0, ans = 0;
for (int right = 0; right < (int) s.size(); right++) {
int c = s[right] - 'a';
cnt[c]++;
while (cnt[c] >= k) {
cnt[s[left] - 'a']--;
left++;
}
ans += left;
}
return ans;
}JavaScript
var numberOfSubstrings = function(s, k) {
var cnt = new Array(26).fill(0);
var left = 0, ans = 0;
for (var right = 0; right < s.length; right++) {
var c = s.charCodeAt(right) - 97;
cnt[c]++;
while (cnt[c] >= k) {
cnt[s.charCodeAt(left) - 97]--;
left++;
}
ans += left;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets