Number of Equal Count Substrings

Number of Equal Count Substrings

What is this problem about?

The Number of Equal Count Substrings problem asks you to count substrings where every character that appears has the same frequency. This is a sliding window problem: for each possible frequency value (1 to n), count substrings where each of the k distinct characters appears exactly that many times (window size = k * freq). This coding problem combines sliding window with character counting.

Why is this asked in interviews?

Cisco asks this to test sliding window with frequency tracking. The constraint "each present character appears equally often" requires checking frequency uniformity within the window. The hash table, counting, sliding window, and string interview pattern is directly applied.

Algorithmic pattern used

Fixed-size sliding window per frequency value. The number of distinct characters in s is at most 26 (call it k). For each possible frequency f from 1 to len(s)/k, check all windows of size k * f. For each window, verify that exactly k distinct characters each appear exactly f times. Count valid windows. Total time: O(26 * n).

Example explanation

s="aabcde", we need all characters in window to appear equally.

• f=1, window_size = distinct_chars * 1. If distinct=5, check all windows of size 5. Window "aabcd": a appears 2 times, not equal. Window "abcde": all appear once ✓. Count += 1.
• f=2, window_size = 10: too large. Stop. Result = 1 (just "abcde" in this case, depending on constraints).

Common mistakes candidates make

• Not iterating over all valid frequency values (only checking f=1).
• Incorrect frequency uniformity check (must verify ALL present characters have equal count).
• Window size calculation error: must be number_of_unique_chars_in_s * f, not total_distinct_in_window * f.
• Not handling the case where window characters include extras beyond the k unique ones.

Interview preparation tip

Fixed-size sliding window problems with "all elements have equal frequency" require: (1) fix the frequency f, (2) compute window size = num_distinct * f, (3) check each window. The check is: exactly num_distinct unique chars each appearing f times. Precomputing the distinct characters in the full string (not the window) is key to the window size formula. Practice "equal frequency character" window problems to build fluency with frequency-uniformity checks.