Problem Description

You are given a string s (0-indexed) containing only lowercase English letters, and an integer count.

An equal count substring is defined as a substring where every unique letter that appears in it occurs exactly count times. For example, if count = 2, then in the substring "aabbcc", each letter ('a', 'b', 'c') appears exactly 2 times, making it an equal count substring.

Your task is to find and return the total number of equal count substrings in the given string s.

A substring is any contiguous sequence of characters within the string. For instance, "abc" has substrings: "a", "b", "c", "ab", "bc", "abc".

Example breakdown:

• If s = "aaabcbbcc" and count = 3, we need to find all substrings where each unique letter appears exactly 3 times
• "aaa" is valid (only 'a' appears, and it appears 3 times)
• "bbb" is valid (only 'b' appears, and it appears 3 times)
• "aaabbb" is NOT valid ('a' appears 3 times, but 'b' also appears 3 times, making it valid actually)
• "aaabcb" is NOT valid ('a' appears 3 times, 'b' appears 2 times, 'c' appears 1 time)

The solution uses a sliding window approach where it iterates through all possible numbers of unique characters (1 to 26), calculates the required window size as number_of_unique_chars * count, and then slides this window across the string while tracking which characters have exactly count occurrences.

Intuition

The key insight is that if we know how many unique characters should be in our substring, we can determine its exact length. If we want i unique characters and each must appear exactly count times, then the substring length must be i * count.

Why enumerate the number of unique characters? Because there are only 26 lowercase English letters, so we can try all possibilities from 1 to 26. This transforms our problem from "find all valid substrings" to "for each possible substring length, find how many valid substrings exist."

For a fixed number of unique characters i, we use a sliding window of size k = i * count. As we slide this window through the string, we need to quickly check if the current window is valid (has exactly i unique characters, each appearing exactly count times).

The clever part is tracking variable t, which counts how many unique characters in the current window appear exactly count times. When a character's frequency becomes exactly count, we increment t. When it moves away from count (either to count+1 or count-1), we decrement t.

As the window slides:

• When adding a new character on the right: we update its count and adjust t accordingly
• When removing a character on the left: we update its count and adjust t accordingly

If at any point t == i, it means all i unique characters in our window appear exactly count times, so we've found a valid substring.

This approach is efficient because instead of checking every possible substring (which would be O(n²) substrings), we only check windows of specific sizes, and for each size, we slide through the string once, giving us O(26 * n) = O(n) time complexity.

Learn more about Sliding Window patterns.

Solution Approach

The implementation uses enumeration combined with a sliding window technique:

1. Enumerate possible unique character counts:

for i in range(1, 27):

We try all possibilities from 1 to 26 unique characters (since there are only 26 lowercase English letters).

2. Calculate window size and early termination:

k = i * count
if k > len(s):
    break

For i unique characters, each appearing count times, the window size is k = i * count. If this exceeds the string length, we can stop since no valid substrings of this size exist.

3. Initialize tracking variables:

• cnt = Counter(): A frequency map to track character counts in the current window
• t = 0: Tracks how many unique characters in the window have exactly count occurrences

4. Slide the window through the string:

for j, c in enumerate(s):
    cnt[c] += 1
    t += cnt[c] == count
    t -= cnt[c] == count + 1

For each new character c entering the window:

• Increment its count in cnt
• If its count becomes exactly count, increment t
• If its count becomes count + 1 (was count before), decrement t

5. Maintain window size by removing leftmost character:

if j >= k:
    cnt[s[j - k]] -= 1
    t += cnt[s[j - k]] == count
    t -= cnt[s[j - k]] == count - 1

When the window exceeds size k:

• Remove the leftmost character s[j - k] by decrementing its count
• If its count becomes exactly count, increment t
• If its count becomes count - 1 (was count before), decrement t

6. Check for valid substring:

ans += i == t

If t == i, all i unique characters in the window appear exactly count times, so we found a valid equal count substring.

The algorithm efficiently processes each possible window size in O(n) time, resulting in an overall time complexity of O(26 * n) = O(n), with O(26) = O(1) space complexity for the character frequency counter.

Example Walkthrough

Let's walk through the solution with s = "aaabcbbcc" and count = 3.

Step 1: Try i = 1 (one unique character, window size = 1 × 3 = 3)

We slide a window of size 3 through the string:

• Window "aaa": cnt = {'a': 3}, t = 1 (since 'a' appears exactly 3 times). Since i = 1 and t = 1, this is valid! ans = 1
• Window "aab": cnt = {'a': 2, 'b': 1}, t = 0 (no character appears exactly 3 times). Not valid.
• Window "abc": cnt = {'a': 1, 'b': 1, 'c': 1}, t = 0. Not valid.
• Window "bcb": cnt = {'b': 2, 'c': 1}, t = 0. Not valid.
• Window "cbb": cnt = {'c': 1, 'b': 2}, t = 0. Not valid.
• Window "bbc": cnt = {'b': 2, 'c': 1}, t = 0. Not valid.
• Window "bcc": cnt = {'b': 1, 'c': 2}, t = 0. Not valid.

Step 2: Try i = 2 (two unique characters, window size = 2 × 3 = 6)

We slide a window of size 6:

• Window "aaabcb": cnt = {'a': 3, 'b': 2, 'c': 1}, t = 1 (only 'a' has count 3). Since i = 2 but t = 1, not valid.
• Window "aabcbb": cnt = {'a': 2, 'b': 3, 'c': 1}, t = 1 (only 'b' has count 3). Not valid.
• Window "abcbbc": cnt = {'a': 1, 'b': 3, 'c': 2}, t = 1. Not valid.
• Window "bcbbcc": cnt = {'b': 3, 'c': 3}, t = 2 (both 'b' and 'c' appear exactly 3 times). Since i = 2 and t = 2, this is valid! ans = 2

Step 3: Try i = 3 (three unique characters, window size = 3 × 3 = 9)

We slide a window of size 9:

• Window "aaabcbbcc": cnt = {'a': 3, 'b': 3, 'c': 3}, t = 3 (all three characters appear exactly 3 times). Since i = 3 and t = 3, this is valid! ans = 3

Step 4: Try i = 4 (four unique characters, window size = 4 × 3 = 12)

Window size 12 > string length 9, so we stop.

Final Answer: 3 equal count substrings

The algorithm efficiently found all valid substrings by:

1. Testing each possible number of unique characters
2. Using a sliding window of the appropriate size
3. Tracking how many characters have the exact required count
4. Incrementing the answer when all unique characters in the window have exactly count occurrences

Solution Implementation

Time and Space Complexity

The time complexity is O(n × C), where n is the length of the string s and C is the number of distinct character types (26 for lowercase English letters).

The outer loop iterates up to 26 times (for i from 1 to 26), representing the number of unique characters in a valid substring. For each iteration i, the inner loop processes the entire string s of length n using a sliding window of size k = i × count. The operations inside the inner loop (updating the counter, adjusting variable t, and checking conditions) all take O(1) time. Therefore, the total time complexity is O(26 × n) = O(n × C).

The space complexity is O(C), where C = 26. The algorithm uses a Counter object cnt to track character frequencies within the sliding window. Since the string contains only lowercase English letters, the counter can store at most 26 different characters, resulting in O(26) = O(C) space complexity. The other variables (ans, i, k, t, j, c) use constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Update Logic for chars_with_exact_count

One of the most common mistakes is mishandling the increment/decrement logic when tracking how many characters have exactly count occurrences. The counter needs to be updated both when adding and removing characters from the window.

Incorrect approach:

# Wrong: Only checking if count equals target, missing the transition cases
if char_counter[current_char] == count:
    chars_with_exact_count += 1

Why it's wrong: When a character's frequency changes from count to count+1, we need to decrement chars_with_exact_count because that character no longer has exactly count occurrences.

Correct approach:

# Update when adding character
if char_counter[current_char] == count:
    chars_with_exact_count += 1
elif char_counter[current_char] == count + 1:
    chars_with_exact_count -= 1  # Was exactly count, now it's count+1

# Update when removing character
if char_counter[left_char] == count:
    chars_with_exact_count += 1  # Now it's exactly count
elif char_counter[left_char] == count - 1:
    chars_with_exact_count -= 1  # Was exactly count, now it's count-1

2. Off-by-One Error in Window Management

Another frequent mistake is incorrectly calculating when to start removing characters from the left side of the window.

Incorrect approach:

# Wrong: Removing too early or too late
if current_index >= window_size - 1:  # or current_index > window_size
    left_char = s[current_index - window_size + 1]  # Wrong index calculation

Correct approach:

# Start removing when we've seen window_size + 1 characters (0-indexed)
if current_index >= window_size:
    left_char = s[current_index - window_size]

3. Not Handling Edge Cases for Small Strings

Failing to handle cases where the string is shorter than the minimum possible window size.

Solution: Always check if window_size > len(s) and break early to avoid unnecessary iterations:

if window_size > len(s):
    break  # No valid substrings possible

4. Forgetting to Reset Variables Between Different Window Sizes

When trying different numbers of unique characters, the char_counter and chars_with_exact_count must be reset for each iteration.

Correct approach: Initialize these variables inside the outer loop:

for num_unique_chars in range(1, 27):
    char_counter = Counter()  # Reset for each window size
    chars_with_exact_count = 0  # Reset for each window size

5. Validation Logic Error

A subtle mistake is checking if the window is valid before it's fully formed.

Solution: Ensure the window has reached its required size before checking validity:

# Only check validity after we have a full window
if current_index >= window_size - 1:  # Window is complete
    if num_unique_chars == chars_with_exact_count:
        result += 1

However, the provided code handles this implicitly since chars_with_exact_count won't equal num_unique_chars until the window is properly formed with the right character distribution.