blob: c971b21c2b33ed6f8d853672d01c43a700316d07 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include "leetcode.h"
class Solution {
public:
int minDeletions(string s) {
vector<int> freq(26, 0);
int ans = 0;
for (char c : s)
freq[c - 'a']++;
sort(freq.begin(), freq.end());
for (int i = 24; i >= 0; i--) {
if (freq[i] == 0)
break;
if (freq[i] >= freq[i + 1]) {
int prev = freq[i];
freq[i] = max(0, freq[i + 1] - 1);
ans += prev - freq[i];
}
}
return ans;
}
};
int main() {
Solution obj;
string s = "aab";
cout << obj.minDeletions(s);
}
|