A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

&nbsp;
Example 1:

Input: s = "aab"
Output: 0
Explanation: s is already good.


Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s&nbsp;contains only lowercase English letters.


class Solution:
    def minDeletions(self, s: str) -> int:
        # Get the frequency of each character sorted in reverse order
        frequencies = sorted(Counter(s).values(), reverse=True)
        
        total_deletions = 0
        next_unused_freq = len(s)
        for freq in frequencies:
            # It is impossible for the frequency to be higher
            next_unused_freq = min(next_unused_freq, freq)
            total_deletions += freq - next_unused_freq

            # We cannot have another character with this frequency,
            # so decrement next_unused_freq
            if next_unused_freq > 0:
                next_unused_freq -= 1

        return total_deletions
class Solution {
    private int N = 26;
    public int minDeletions(String s) {
        int[] array = new int[N];
        for (char ch : s.toCharArray()) {
            array[ch - 'a']++;
        }
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int i : array) {
            if (i == 0) continue;
            while (set.contains(i)) {
                i--;
                ans++;
            }
            if (i != 0) {
                set.add(i);
            }
        }
        return ans;
    }
}
class Solution {
public:
    int minDeletions(string s) {
        //Array to store the count of each character.
        vector<int> freq (26, 0);
        
        //Calculatimg frequency of all characters.
        for (char c : s){
            freq[c - 'a']++;
        }
        
        //sorting the frequencies. So the greatest frequencies are in right side.
        sort(freq.begin(), freq.end());
        
        int del = 0; //to store the deletions.
        
        //Checking if 2 frequencies are same, if same then decrease the frequency so that it becomes less than the next greater one.So Start from the 2nd greatest frequency that is at freq[24].
        for (int i = 24; i >= 0; i--) {
            
            if(freq[i] == 0) break; // if frequency is 0 that means no more character is left.
            
            if(freq[i] >= freq[i+1]){
                int prev = freq[i]; //To store the frequency before deletion.
                freq[i] = max(0, freq[i+1] -1); //New frequency should be 1 less than the previous frequency in the array.
                del += prev - freq[i]; //Calculating deleted characters 
            }
        }
        return del;
    }
};
var minDeletions = function(s) {
    let freq = new Array(26).fill(0); // Create an array to store character frequencies
    
    for (let i = 0; i < s.length; i++) {
        freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; // Count the frequency of each character
    }
    
    freq.sort((a, b) => a - b); // Sort frequencies in ascending order
    
    let del = 0; // Initialize the deletion count
    
    for (let i = 24; i >= 0; i--) {
        if (freq[i] === 0) {
            break; // No more characters with this frequency
        }
        
        if (freq[i] >= freq[i + 1]) {
            let prev = freq[i];
            freq[i] = Math.max(0, freq[i + 1] - 1);
            del += prev - freq[i]; // Update the deletion count
        }
    }
    
    return del; // Return the minimum deletions required
};
Minimum Deletions to Make Character Frequencies Unique