# Count Substrings With K-Frequency Characters I **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-substrings-with-k-frequency-characters-i) Canonical: https://scaleengineer.com/dsa/problems/count-substrings-with-k-frequency-characters-i **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Hash Table, String --- ## Problem 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 <= 3000` * `1 <= k <= s.length` * `s` consists only of lowercase English letters. # Approaches ## Brute-Force Enumeration 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. **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). **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm - Initialize a counter `ans` to 0. - Use two nested loops with indices `i` and `j` to generate all substrings `s[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 `k` or more, increment `ans` and break the check for the current substring. - After checking all substrings, return `ans`. ## Optimized Iteration with Early Exit 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. **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. **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. ### Explanation 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`. ```java 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; } } ``` ### Algorithm - Initialize a counter `ans` to 0. - Iterate through the string with an outer loop for the start index `i` from `0` to `n-1`. - For each `i`, initialize a new frequency map. - Start an inner loop for the end index `j` from `i` to `n-1`. - Update the frequency of `s.charAt(j)` in the map. - If the frequency of `s.charAt(j)` reaches `k`, it means the substring `s[i..j]` and all subsequent substrings starting at `i` are valid. - Add the number of these valid substrings (`n - j`) to `ans`. - Break the inner loop and continue with the next start index `i`. - Return `ans`. ## Sliding Window with Complementary Counting 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. **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). **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. ### Explanation 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. ```java 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); } } ``` ### Algorithm - Calculate the total number of substrings: `total = n * (n + 1) / 2`. - Initialize a counter for 'invalid' substrings `invalidCount` to 0, a `left` pointer to 0, and a frequency map. - Iterate through the string with a `right` pointer from `0` to `n-1`. - For each `right`, increment the frequency of `s.charAt(right)`. - While the frequency of `s.charAt(right)` is `>= k`, shrink the window by decrementing the frequency of `s.charAt(left)` and incrementing `left`. - After the window is valid again (all character frequencies `< k`), the number of invalid substrings ending at `right` is `right - left + 1`. Add this to `invalidCount`. - After the loop, the final result is `total - invalidCount`. # Solutions ### Java ```java 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; } } ``` ### CPP ```cpp 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; } }; ``` ### Python ```python 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 ```