Unique Substrings With Equal Digit Frequency - Solution & Explanation

Problem Overview: Given a numeric string s, count how many distinct substrings exist where every digit that appears in the substring occurs the same number of times. The substring 1212 is valid because both digits appear twice, while 1123 is not because frequencies differ.

Approach 1: Brute Force Enumeration with Frequency Check (O(n^3) time, O(n^2) space)

Generate every substring using two nested loops. For each substring, compute digit frequencies using an array of size 10 and verify that all non‑zero counts are equal. Store valid substrings in a hash set to ensure uniqueness. The validation step scans up to 10 digits, and substring creation costs additional time, pushing the total complexity toward O(n^3). This approach is straightforward and demonstrates the core constraint but becomes slow for longer strings.

Approach 2: Rolling Expansion + Frequency Counting + Hash Set (O(n^2) time, O(n^2) space)

Fix a starting index and extend the substring one character at a time. Maintain a frequency array for digits 0–9, track the number of distinct digits, and keep the maximum frequency seen so far. A substring is valid when maxFreq * distinctDigits == length. This works because equal frequency means each distinct digit must appear exactly length / distinctDigits times.

To count only unique substrings, compute a rolling hash while expanding the window and insert it into a hash set. Each extension updates the digit count and hash in constant time. Since each start index expands at most n positions, the algorithm runs in O(n^2) time with O(n^2) space for the set of hashes. This approach combines hash tables, string processing, and rolling hash to efficiently avoid duplicate substring storage.

Recommended for interviews: Start by describing the brute force substring enumeration to show understanding of the constraint. Then optimize by expanding substrings incrementally and checking the maxFreq * distinct == length condition while storing hashes in a set. Interviewers typically expect the O(n^2) approach because it demonstrates efficient substring iteration, frequency counting, and hash-based deduplication.