1781. Sum of Beauty of All Substrings
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
- For example, the beauty of “abaacc” is 3 - 1 = 2.
Given a string s, return the sum of beauty of all of its substrings.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int beautySum(string s) {
int res = 0, n = s.length();
for(int i = 0; i < n; i++) {
int freq[26] = {0,}, ma = 0, mi = 0;
for(int j = i; j < n; j++) {
int idx = s[j] - 'a';
freq[idx]++;
ma = max(ma, freq[idx]);
if(freq[idx] - 1 == mi) {
mi = INT_MAX;
for(int k = 0; k < 26; k++) {
if(freq[k] == 0) continue;
mi = min(mi, freq[k]);
}
} else if(freq[idx] < mi) mi = freq[idx];
res += ma - mi;
}
}
return res;
}
};
|
