[LeetCode] Unique Substrings With Equal Digit Frequency

2168. Unique Substrings With Equal Digit Frequency

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

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
long long mod = 1e9 + 7;
long long h = 31;
public:
int equalDigitFrequency(string s) {
unordered_set<long long> us;
for(int i = 0; i < s.length(); i++) {
long long hash = 0, ma = 0, uniq = 0;
vector<long long> freq(10);
for(int j = i; j < s.length(); j++) {
int d = s[j] - '0';
if(++freq[d] == 1) uniq++;
ma = max(ma, freq[d]);
hash = (hash * h + d + 1) % mod;
if(ma * uniq == j - i + 1)
us.insert(hash);
}
}

return us.size();
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/08/02/PS/LeetCode/unique-substrings-with-equal-digit-frequency/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.

Gitalking ...