Count Substrings With K-Frequency Characters II
Count substrings of s where at least one character appears at least k times — atLeast counting via sliding window.
3 min read
sliding-window string hash-map
Problem#
Count substrings of s such that at least one character appears at least k times.
Examples#
s = "abacb", k = 2→4("aba","abac","abacb","bacb")s = "abcde", k = 1→15
Constraints#
1 <= s.length <= 3 * 10^5,1 <= k <= s.length.
Hints#
Hint 1
For each
right, find the smallest left such that some character appears ≥ k times in [left..right]. All left' ≤ left work too. Approach#
Track frequencies. Expand right; while some count reaches k, the window is valid. Advance left to record the smallest valid left for that right; all starts ≤ left produce valid substrings ending at right.
Solution#
class Solution {public: long long numberOfSubstrings(string s, int k) { int count[26] = {0}; long long ans = 0; int left = 0; for (int right = 0; right < (int)s.size(); ++right) { ++count[s[right] - 'a']; while (count[s[right] - 'a'] >= k) { --count[s[left++] - 'a']; } ans += left; } return ans; }};func numberOfSubstrings(s string, k int) int64 { var count [26]int var ans int64 left := 0 for right := 0; right < len(s); right++ { count[s[right]-'a']++ for count[s[right]-'a'] >= k { count[s[left]-'a']-- left++ } ans += int64(left) } return ans}class Solution: def numberOfSubstrings(self, s: str, k: int) -> int: count = [0] * 26 ans = 0 left = 0 for right in range(len(s)): idx = ord(s[right]) - ord('a') count[idx] += 1 while count[idx] >= k: count[ord(s[left]) - ord('a')] -= 1 left += 1 ans += left return ansfunction numberOfSubstrings(s, k) { const count = new Array(26).fill(0); let ans = 0; let left = 0; for (let right = 0; right < s.length; right++) { const idx = s.charCodeAt(right) - 97; count[idx]++; while (count[idx] >= k) { count[s.charCodeAt(left) - 97]--; left++; } ans += left; } return ans;}class Solution { public long numberOfSubstrings(String s, int k) { int[] count = new int[26]; long ans = 0; int left = 0; for (int right = 0; right < s.length(); right++) { int idx = s.charAt(right) - 'a'; count[idx]++; while (count[idx] >= k) { count[s.charAt(left) - 'a']--; left++; } ans += left; } return ans; }}function numberOfSubstrings(s: string, k: number): number { const count: number[] = new Array(26).fill(0); let ans = 0; let left = 0; for (let right = 0; right < s.length; right++) { const idx = s.charCodeAt(right) - 97; count[idx]++; while (count[idx] >= k) { count[s.charCodeAt(left) - 97]--; left++; } ans += left; } return ans;}Editorial#
The slick observation: once the window first becomes valid at right, every shorter prefix start [0, left) still yields a valid substring ending at right. So ans += left counts them en bloc. We track only the character that just crossed k because that’s the only one whose count could have triggered validity.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#