You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count. A substring of s is said to be an equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.
Return the number of equal count substrings in s.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "aaabcbbcc", count = 3 Output: 3 Explanation: The substring that starts at index 0 and ends at index 2 is "aaa". The letter 'a' in the substring appears exactly 3 times. The substring that starts at index 3 and ends at index 8 is "bcbbcc". The letters 'b' and 'c' in the substring appear exactly 3 times. The substring that starts at index 0 and ends at index 8 is "aaabcbbcc". The letters 'a', 'b', and 'c' in the substring appear exactly 3 times.
Example 2:
Input: s = "abcd", count = 2 Output: 0 Explanation: The number of times each letter appears in s is less than count. Therefore, no substrings in s are equal count substrings, so return 0.
Example 3:
Input: s = "a", count = 5 Output: 0 Explanation: The number of times each letter appears in s is less than count. Therefore, no substrings in s are equal count substrings, so return 0
Constraints:
1 <= s.length <= 3 * 1041 <= count <= 3 * 104s consists only of lowercase English letters.Problem Overview: Given a string s and an integer count, the task is to count substrings where every distinct character appears exactly count times. If a substring contains k distinct characters, its length must be k * count and each of those characters must occur exactly count times.
Approach 1: Brute Force Enumeration (O(n^2 * 26) time, O(26) space)
Generate every possible substring using two nested loops. Maintain a frequency array of size 26 while expanding the right boundary. For each substring, check whether all characters that appear do so exactly count times and the total length equals distinct * count. The validation step requires scanning the frequency array to confirm the condition. This approach is straightforward and useful for understanding the constraint structure, but the quadratic enumeration becomes too slow for larger inputs.
Approach 2: Enumeration + Sliding Window (O(26 * n) time, O(26) space)
Instead of checking all substrings, iterate over the possible number of distinct characters k from 1 to 26. For each k, the only valid substring length is k * count. Use a sliding window of that size and maintain character frequencies with a fixed array. As the window moves, update counts for the entering and leaving characters. Track how many characters currently appear exactly count times. When the window length equals k * count and exactly k characters meet the frequency requirement, you found a valid substring.
The key insight: valid substrings have a fixed length determined by the number of distinct characters. Enumerating k removes the need to re-check every frequency combination. Each window update takes constant time, giving a linear scan per k. This pattern combines frequency counting with the classic string sliding window technique.
Recommended for interviews: The enumeration + sliding window approach is the expected solution. Brute force demonstrates understanding of the substring constraint, but the optimized version shows you can reduce the search space by fixing substring length and using efficient frequency updates. Interviewers often look for this transition from naive enumeration to a controlled window using counting logic and prefix-style state tracking similar to ideas used in prefix sum problems.
We can enumerate the number of types of letters in the substring within the range of [1..26], then the length of the substring is i times count.
Next, we take the current substring length as the size of the window, count the number of types of letters in the window size that are equal to count, and record it in t. If i = t at this time, it means that the number of letters in the current window are all count, then we can increment the answer by one.
The time complexity is O(n times C), and the space complexity is O(C). Where n is the length of the string s, and C is the number of types of letters, in this problem C = 26.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2 * 26) | O(26) | For conceptual understanding or very small inputs |
| Enumeration + Sliding Window | O(26 * n) | O(26) | Optimal general solution using fixed window length and frequency counting |
Leetcode 2067. Number of Equal Count Substrings (fixed sliding window) • LetsCode • 110 views views
Watch 2 more video solutions →Practice Number of Equal Count Substrings with our built-in code editor and test cases.
Practice on FleetCode