Skip to main content
Talentd

Unique Substrings With Equal Digit Frequency - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringRolling HashCounting4 min readAsked at: Expedia
Practice this problem

Problem Statement

Given a digit string s, return the number of unique substrings of s where every digit appears the same number of times.

 

Example 1:

Input: s = "1212"
Output: 5
Explanation: The substrings that meet the requirements are "1", "2", "12", "21", "1212".
Note that although the substring "12" appears twice, it is only counted once.

Example 2:

Input: s = "12321"
Output: 9
Explanation: The substrings that meet the requirements are "1", "2", "3", "12", "23", "32", "21", "123", "321".

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of digits.

Approach Overview

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.

Solution

Code

PythonJavaGo

Python

Java

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^3)O(n^2)Conceptual baseline or when constraints are very small
Rolling Expansion + Frequency Counting + Hash SetO(n^2)O(n^2)General case; avoids recomputing frequencies and ensures unique substrings efficiently

Video Solution

【每日一题】LeetCode 2168. Unique Substrings With Equal Digit Frequency • Huifeng Guan • 447 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Unique Substrings With Equal Digit Frequency easy or hard?
The problem is rated Medium on LeetCode. The main challenge is recognizing the mathematical condition maxFreq × distinctDigits = substring length and combining it with hashing to count only unique substrings efficiently.
Unique Substrings With Equal Digit Frequency Python/Java solution
Implement two nested loops to expand substrings, maintain a digit frequency array, and compute a rolling hash for each extension. When maxFreq × distinctDigits equals the substring length, add the hash to a set. The same logic translates directly to Python, Java, or Go with O(n^2) complexity.
How to solve Unique Substrings With Equal Digit Frequency in O(n^2)?
Fix a starting index and extend the substring one character at a time. Maintain a frequency array for digits 0–9, track distinct digits, and record the maximum frequency. If maxFreq × distinctDigits equals the current substring length, the substring has equal digit frequency. Insert its rolling hash into a set to ensure uniqueness.
What is the best approach for Unique Substrings With Equal Digit Frequency?
The optimal approach expands substrings from each starting index while maintaining digit frequencies. Track the number of distinct digits and the maximum frequency. A substring is valid when maxFreq × distinctDigits equals the substring length. Use a hash set with rolling hash to store unique substrings. This runs in O(n^2) time.
Is Unique Substrings With Equal Digit Frequency asked at Google/Amazon/Meta?
Problems involving substring hashing, frequency counting, and uniqueness checks are common in interviews at companies like Google, Amazon, and Meta. Variations using rolling hash or substring frequency constraints frequently appear in medium-level string questions.
What data structure is used in Unique Substrings With Equal Digit Frequency?
The solution primarily uses a frequency array of size 10 for digit counting and a hash set to store unique substring hashes. Rolling hash is used to represent substrings efficiently without storing the entire string each time.
What is the time complexity of Unique Substrings With Equal Digit Frequency?
The optimized solution runs in O(n^2) time because each starting index expands at most n positions while updating counts in constant time. Space complexity is O(n^2) for storing hashes of unique substrings.

Ready to solve this problem?

Practice Unique Substrings With Equal Digit Frequency with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Equal Count Substrings

Next

Substrings That Begin and End With the Same Letter