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 <= 1000sconsists of digits.
Companies:
Expedia
Related Topics:
Hash Table, String, Rolling Hash, Counting, Hash Function
Similar Questions:
- Number of Equal Count Substrings (Medium)
- Substrings That Begin and End With the Same Letter (Medium)
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();
}
};