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.lengths consists only of lowercase English letters.Problem Overview: Given a string s and an integer k, count how many substrings contain at least one character that appears k or more times within that substring. The challenge is efficiently checking frequency conditions across all possible substrings.
Approach 1: Brute Force Frequency Counting (O(n^2 * 26) time, O(26) space)
Generate every substring using two nested loops. For each starting index, extend the substring one character at a time while maintaining a frequency array or hash map. After adding each character, check if any character frequency reaches k. If it does, the current substring is valid. This approach is straightforward and demonstrates the core idea, but it becomes slow for large inputs because it evaluates nearly every substring.
This method relies on simple character counting using a hash table or fixed array. It is useful for understanding the problem constraints and verifying correctness before optimizing.
Approach 2: Sliding Window with HashMap (O(n) time, O(26) space)
A more efficient strategy uses a sliding window with two pointers. Expand the right pointer while tracking character frequencies in a hash map. Once any character count becomes k, the current window guarantees that every substring extending further to the right will also satisfy the condition. That means you can immediately add n - right valid substrings to the result.
After counting them, move the left pointer to shrink the window and update frequencies. This ensures the window continues exploring new valid ranges without recomputing counts from scratch. The key insight is that once the frequency threshold is reached, all longer substrings starting at the same left index remain valid.
This approach processes each character a constant number of times, producing linear time complexity. It combines frequency tracking from hash tables with the efficient boundary movement pattern used in many string window problems.
Recommended for interviews: Start by describing the brute force enumeration to show you understand the substring search space. Then move to the sliding window optimization. Interviewers typically expect the O(n) sliding window solution because it demonstrates strong control of two-pointer techniques and frequency tracking.
In this approach, we generate all possible substrings of the given string s. For each substring, we maintain a frequency count of characters and check if there exists at least one character with a frequency greater than or equal to k. This method is simple but not the most efficient due to its time complexity.
This C solution uses nested loops to generate all substrings. An array freq of size 26 is used to keep the frequency of each character as we extend the substring in the inner loop. If any character's frequency becomes ≥ k, we increment the count of valid substrings and break the inner loop.
Time Complexity: O(n^3), where n is the length of the string.
Space Complexity: O(1), auxiliary space used for the frequency array.
This approach utilizes a sliding window technique with a hash map to effectively manage the frequency of characters in the current window (substring). The window dynamically expands and shrinks while maintaining character frequency information, allowing us to update the count of valid substrings efficiently.
This Python solution utilizes a sliding window over the string s. For each starting position, it expands the window and maintains a frequency map for characters in the current substring, incrementing the result count when any character reaches a frequency ≥ k.
Python
Time Complexity: Roughly O(n^2), depending on hash map operations
Space Complexity: O(1) considering limited variable-size growth (bounded by 26 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 k.
We can use an array cnt to maintain the occurrence count of each character in the sliding window, then use a variable l to maintain the left endpoint of the sliding window, and use a variable ans to maintain the answer.
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 k. If it is, we remove the character at the left endpoint from the sliding window until the occurrence count of each character in the sliding window is less than k. At this point, for substrings with left endpoints in the range [0, ..l - 1] and right endpoint r, all satisfy the problem's requirements, so we add l to the answer.
After enumeration, we return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, which in this case is the set of lowercase letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where |
| Sliding Window with HashMap | Time Complexity: Roughly O(n^2), depending on hash map operations |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Count | O(n^2 * 26) | O(26) | When first reasoning about substring enumeration or validating logic on small inputs |
| Sliding Window with HashMap | O(n) | O(26) | Best general solution for large strings where efficient substring counting is required |
Leetcode Weekly Contest 420 | 3325. Count Substrings With K-Frequency Characters I | CodeFod • CodeFod • 886 views views
Watch 3 more video solutions →Practice Count Substrings With K-Frequency Characters I with our built-in code editor and test cases.
Practice on FleetCode