Minimum Deletions to Make Character Frequencies Unique LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minDeletions(string s) {
4
    // Array to store the count of each character.
5
    vector<int> freq(26, 0);
6

7
    // Calculatimg frequency of all characters.
8
    for (char c : s) {
9
      freq[c - 'a']++;
10
    }
11

12
    // sorting the frequencies. So the greatest frequencies are in right side.
13
    sort(freq.begin(), freq.end());
14

15
    int del = 0; // to store the deletions.
16

17
    // Checking if 2 frequencies are same, if same then decrease the frequency
18
    // so that it becomes less than the next greater one.So Start from the 2nd
19
    // greatest frequency that is at freq[24].
20
    for (int i = 24; i >= 0; i--) {
21
      if (freq[i] == 0) break; // if frequency is 0 that means no more character is left.
22

23
      if (freq[i] >= freq[i + 1]) {
24
        int prev = freq[i];                // To store the frequency before deletion.
25
        freq[i] = max(0, freq[i + 1] - 1); // New frequency should be 1 less than the
26
                                           // previous frequency in the array.
27
        del += prev - freq[i];             // Calculating deleted characters
28
      }
29
    }
30
    return del;
31
  }
32
};