##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2168.html

# 2168. Unique Substrings With Equal Digit Frequency (Medium)

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.

Companies:
Expedia

Related Topics:
Hash Table, String, Rolling Hash, Counting, Hash Function

Similar Questions:

## Solution 1.

// OJ: https://leetcode.com/problems/unique-substrings-with-equal-digit-frequency/
// Time: O(N^3)
// Space: O(N^2)
class Solution {
public:
int equalDigitFrequency(string s) {
int N = s.size();
unordered_set<string> ans;
for (int i = 0; i < N; ++i) {
int cnt[10] = {};
for (int j = i; j < N; ++j) {
cnt[s[j] - '0']++;
int k = 0, c = -1;
for (; k < 10; ++k) {
if (cnt[k] == 0) continue;
if (c == -1) c = cnt[k];
if (cnt[k] != c) break;
}
if (k == 10) ans.insert(s.substr(i, j - i + 1));
}
}
return ans.size();
}
};


## Solution 2. Rabin Karp

// OJ: https://leetcode.com/problems/unique-substrings-with-equal-digit-frequency/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int equalDigitFrequency(string s) {
unordered_set<int> ans;
for (int i = 0, N = s.size(); i < N; ++i) {
long long cnt[11] = {}, unique = 0, mxCnt = 0, hash = 0;
for (int j = i; j < N; ++j) {
int d = s[j] - '0';
mxCnt = max(mxCnt, ++cnt[d]);
unique += cnt[d] == 1;
hash = (hash * 11 + d + 1) % 1000000007;
if (mxCnt * unique == j - i + 1) ans.insert(hash);
}
}
return ans.size();
}
};