aboutsummaryrefslogtreecommitdiff
path: root/min_deletions_unique_char.cpp
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);
}