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 <= 3 * 1051 <= 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 whose frequency in that substring reaches k. The brute force approach checks every substring, but the optimal solution uses a sliding window and frequency tracking to count valid substrings efficiently.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Generate every possible substring using two nested loops. For each starting index, expand the substring one character at a time and maintain a frequency counter. As soon as any character reaches frequency k, the current substring and all longer substrings starting at the same index are valid. Increment the answer accordingly. This approach is simple and demonstrates the core condition, but checking up to O(n^2) substrings makes it too slow for large inputs.
Approach 2: Sliding Window with Frequency Counting (O(n) time, O(1) space)
The optimal method uses a classic sliding window. Maintain two pointers left and right that define the current window and track character frequencies using a small array or hash table. As you expand the window by moving right, update the frequency of the current character. When a character's count reaches k, the window satisfies the condition.
At that point, every substring ending at right and starting anywhere from 0 to left contributes to the result. Shrink the window from the left while the condition still holds to find the minimal valid start. Each step maintains valid frequency counts and ensures each character enters and leaves the window at most once, producing linear time complexity.
This approach works because the constraint depends only on character counts inside the window. Using a frequency array for lowercase letters keeps space constant. The algorithm processes the string once, updating counts and adjusting pointers without revisiting characters.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see whether you recognize that substring counting problems often reduce to maintaining a dynamic window and frequency map. Explaining the brute force first shows understanding of the problem constraints, while implementing the optimized sliding window demonstrates mastery of string processing and two‑pointer techniques.
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 | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Useful for understanding the substring condition or validating logic on small inputs |
| Sliding Window with Frequency Map | O(n) | O(1) | Optimal solution for large strings; processes each character once using two pointers |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views
Watch 9 more video solutions →Practice Count Substrings With K-Frequency Characters II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor