Count Substrings With K-Frequency Characters I - Solution & Explanation
Problem Statement
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.
Approach Overview
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.
Approach 1: Brute Force Approach
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.
Complexity
Time Complexity: O(n^3), where n is the length of the string.
Space Complexity: O(1), auxiliary space used for the frequency array.
Approach 2: Sliding Window with HashMap
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.
Code
Python
Complexity
Time Complexity: Roughly O(n^2), depending on hash map operations
Space Complexity: O(1) considering limited variable-size growth (bounded by 26 letters).
Approach 3: Sliding Window
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Substrings With K-Frequency Characters I || LeetCode Weekly Contest 420 || Leetcode Solution • codi • 1,341 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Count Substrings With K-Frequency Characters I easy or hard?
Count Substrings With K-Frequency Characters I Python/Java solution
How to solve Count Substrings With K-Frequency Characters I in O(n)?
What is the best approach for Count Substrings With K-Frequency Characters I?
Is Count Substrings With K-Frequency Characters I asked at Google/Amazon/Meta?
What data structure is used in Count Substrings With K-Frequency Characters I?
What is the time complexity of Count Substrings With K-Frequency Characters I?
Ready to solve this problem?
Practice Count Substrings With K-Frequency Characters I with our built-in code editor and test cases.
Practice on FleetCode