Count Substrings With K-Frequency Characters I
MedPrompt
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 <= 30001 <= k <= s.lengthsconsists only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward method is to generate all possible substrings of the input string s. For each substring, we then count the frequency of its characters to determine if it satisfies the condition of having at least one character appear k or more times.
Algorithm
- Initialize a counter
ansto 0. - Use two nested loops with indices
iandjto generate all substringss[i..j]. - For each substring, create a frequency map (an array of size 26).
- Iterate through the characters of the substring to populate the frequency map.
- Check the frequency map. If any character has a frequency of
kor more, incrementansand break the check for the current substring. - After checking all substrings, return
ans.
Walkthrough
This approach uses three nested loops. The first two loops define the start and end indices of a substring. The third loop iterates through the characters of this substring to build a frequency map. After building the map, we check if any character's frequency is at least k. If the condition is met, we increment a counter.
class Solution { public int countSubstrings(String s, int k) { int n = s.length(); int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Substring is s.substring(i, j + 1) int[] freq = new int[26]; for (int l = i; l <= j; l++) { freq[s.charAt(l) - 'a']++; } boolean found = false; for (int f : freq) { if (f >= k) { found = true; break; } } if (found) { count++; } } } return count; }}Complexity
Time
O(n^3), where `n` is the length of the string. Generating all O(n^2) substrings and then iterating through each one (which can be up to length `n`) to count frequencies leads to a cubic time complexity.
Space
O(1), as the frequency map uses a constant amount of space (size 26).
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient due to redundant calculations.
Will likely result in a 'Time Limit Exceeded' error for the given constraints.
This approach improves upon the brute-force method by optimizing the process of checking substrings. Instead of re-calculating character frequencies for each substring from scratch, we fix the starting point of a substring and extend its end point one character at a time, maintaining a running frequency count. A key observation is that if a substring s[i..j] is valid (has a character with frequency >= k), then any longer substring starting at i, i.e., s[i..p] where p > j, will also be valid. This allows us to count all such valid substrings at once and move to the next starting point.
Algorithm
- Initialize a counter
ansto 0. - Iterate through the string with an outer loop for the start index
ifrom0ton-1. - For each
i, initialize a new frequency map. - Start an inner loop for the end index
jfromiton-1. - Update the frequency of
s.charAt(j)in the map. - If the frequency of
s.charAt(j)reachesk, it means the substrings[i..j]and all subsequent substrings starting atiare valid. - Add the number of these valid substrings (
n - j) toans. - Break the inner loop and continue with the next start index
i. - Return
ans.
Walkthrough
We use two nested loops. The outer loop fixes the starting index i. The inner loop iterates from i to the end of the string, extending the substring. We maintain a frequency map for the current substring s[i..j]. When we find the first j for which s[i..j] is valid, we know that all substrings starting at i and ending at j or later are also valid. There are n - j such substrings. We add this to our total count and break the inner loop to move to the next starting index i.
class Solution { public int countSubstrings(String s, int k) { int n = s.length(); int count = 0; for (int i = 0; i < n; i++) { int[] freq = new int[26]; for (int j = i; j < n; j++) { freq[s.charAt(j) - 'a']++; if (freq[s.charAt(j) - 'a'] >= k) { // The substring s[i..j] is valid. // All substrings starting at i and ending at j or later are also valid. // These are s[i..j], s[i..j+1], ..., s[i..n-1]. // There are (n - 1) - j + 1 = n - j such substrings. count += (n - j); break; // Move to the next starting point i. } } } return count; }}Complexity
Time
O(n^2), where `n` is the length of the string. We have two nested loops, and the operations inside are constant time.
Space
O(1), as the frequency map is re-initialized for each starting position and has a constant size of 26.
Trade-offs
Pros
More efficient than the pure brute-force approach.
Still relatively easy to understand.
Cons
The O(n^2) complexity might be too slow for problems with larger constraints, although it passes for this specific problem.
The most efficient approach uses the principle of complementary counting combined with a sliding window. Instead of directly counting substrings where at least one character appears k or more times, we count the substrings that do not satisfy this condition and subtract this count from the total number of possible substrings. A substring fails the condition if all of its characters appear strictly fewer than k times.
Algorithm
- Calculate the total number of substrings:
total = n * (n + 1) / 2. - Initialize a counter for 'invalid' substrings
invalidCountto 0, aleftpointer to 0, and a frequency map. - Iterate through the string with a
rightpointer from0ton-1. - For each
right, increment the frequency ofs.charAt(right). - While the frequency of
s.charAt(right)is>= k, shrink the window by decrementing the frequency ofs.charAt(left)and incrementingleft. - After the window is valid again (all character frequencies
< k), the number of invalid substrings ending atrightisright - left + 1. Add this toinvalidCount. - After the loop, the final result is
total - invalidCount.
Walkthrough
The total number of substrings in a string of length n is n * (n + 1) / 2. We find the number of 'invalid' substrings (where all character frequencies are < k) using a single-pass sliding window.
We maintain a window [left, right] and a frequency map. We iterate right from 0 to n-1, expanding the window. If adding s.charAt(right) causes its frequency to become k, we must shrink the window from the left by incrementing left until the frequency is back below k.
After adjusting left, the window s[left..right] is the longest substring ending at right where all character frequencies are < k. Any substring ending at right and starting at an index i where left <= i <= right also has this property. The number of such substrings is right - left + 1. We sum these counts for all right to get the total number of 'invalid' substrings.
The final answer is the total number of substrings minus this count.
class Solution { public int countSubstrings(String s, int k) { long n = s.length(); long totalSubstrings = n * (n + 1) / 2; // Count the complement: substrings where ALL character frequencies are LESS THAN k. long invalidSubstringsCount = 0; int[] freq = new int[26]; int left = 0; for (int right = 0; right < n; right++) { freq[s.charAt(right) - 'a']++; // If the frequency of the character at 'right' reaches k, // our window is no longer "invalid". We must shrink it from the left. while (freq[s.charAt(right) - 'a'] >= k) { freq[s.charAt(left) - 'a']--; left++; } // The window s[left..right] now satisfies the condition that all character frequencies are < k. // Any substring ending at 'right' and starting from 'left' onwards also satisfies this. invalidSubstringsCount += (right - left + 1); } return (int)(totalSubstrings - invalidSubstringsCount); }}Complexity
Time
O(n), where `n` is the length of the string. Both `left` and `right` pointers traverse the string at most once.
Space
O(1), as the frequency map uses a constant amount of space (size 26).
Trade-offs
Pros
Most efficient solution with linear time complexity.
Scales well for very large inputs.
Cons
The logic of complementary counting can be less intuitive to come up with compared to direct approaches.
Solutions
Solution
class Solution {public int numberOfSubstrings(String s, int k) { int[] cnt = new int[26]; int ans = 0, l = 0; for (int 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: int numberOfSubstrings(string s, int k) { int n = s.size(); int 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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.