Unique Substrings With Equal Digit Frequency solution and explanation
3 more videos on this problem
【每日一题】LeetCode 2168. Unique Substrings With Equal Digit FrequencyHuifeng Guan · 21:05 · 447 views
2168. Unique Substrings With Equal Digit Frequency - Week 2/5 Leetcode January ChallengeProgramming Live with Larry · 11:50 · 400 views
2168. Unique Substrings With Equal Digit Frequency (Leetcode Medium)Programming Live with Larry · 13:33 · 299 views
Unique Substrings With Equal Digit FrequencyOwen Wu · 3:10 · 81 views
The problem
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 <= 1000sconsists 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
class Solution:
def equalDigitFrequency(self, s: str) -> int:
def check(i, j):
v = set()
for k in range(10):
cnt = presum[j + 1][k] - presum[i][k]
if cnt > 0:
v.add(cnt)
if len(v) > 1:
return False
return True
n = len(s)
presum = [[0] * 10 for _ in range(n + 1)]
for i, c in enumerate(s):
presum[i + 1][int(c)] += 1
for j in range(10):
presum[i + 1][j] += presum[i][j]
vis = set(s[i : j + 1] for i in range(n) for j in range(i, n) if check(i, j))
return len(vis)class Solution {
public int equalDigitFrequency(String s) {
int n = s.length();
int[][] presum = new int[n + 1][10];
for (int i = 0; i < n; ++i) {
++presum[i + 1][s.charAt(i) - '0'];
for (int j = 0; j < 10; ++j) {
presum[i + 1][j] += presum[i][j];
}
}
Set<String> vis = new HashSet<>();
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (check(i, j, presum)) {
vis.add(s.substring(i, j + 1));
}
}
}
return vis.size();
}
private boolean check(int i, int j, int[][] presum) {
Set<Integer> v = new HashSet<>();
for (int k = 0; k < 10; ++k) {
int cnt = presum[j + 1][k] - presum[i][k];
if (cnt > 0) {
v.add(cnt);
}
if (v.size() > 1) {
return false;
}
}
return true;
}
}func equalDigitFrequency(s string) int {
n := len(s)
presum := make([][]int, n+1)
for i := range presum {
presum[i] = make([]int, 10)
}
for i, c := range s {
presum[i+1][c-'0']++
for j := 0; j < 10; j++ {
presum[i+1][j] += presum[i][j]
}
}
check := func(i, j int) bool {
v := make(map[int]bool)
for k := 0; k < 10; k++ {
cnt := presum[j+1][k] - presum[i][k]
if cnt > 0 {
v[cnt] = true
}
if len(v) > 1 {
return false
}
}
return true
}
vis := make(map[string]bool)
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
if check(i, j) {
vis[s[i:j+1]] = true
}
}
}
return len(vis)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^3) | O(n^2) | Conceptual baseline or when constraints are very small |
| Rolling Expansion + Frequency Counting + Hash Set | O(n^2) | O(n^2) | General case; avoids recomputing frequencies and ensures unique substrings efficiently |
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.