1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int beautySum(string s) {
const int n = s.size();
int ans = 0;
vector<int> dp(26);
map<int, int> m;
for (int i = 0; i < n; ++i) {
fill(dp.begin(), dp.end(), 0);
m.clear();
for (int j = i; j < n; ++j) {
const int c = ++dp[s[j] - 'a'];
++m[c];
if (c > 1) {
auto it = m.find(c - 1);
if (--it->second == 0)
m.erase(it);
}
ans += m.rbegin()->first - m.begin()->first;
}
}
return ans;
}
};
|