Watch 3 video solutions for Number of Equal Count Substrings, a medium level problem involving String, Counting, Prefix Sum. This walkthrough by LetsCode has 110 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |