> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/hash-and-map/1647.-minimum-deletions-to-make-character-frequencies-unique.md).

# 1647. Minimum Deletions to Make Character Frequencies Unique

## Problem Statement

<br>

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`.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "aab"
</strong><strong>Output: 0
</strong><strong>Explanation: s is already good.
</strong></code></pre>

**Example 2:**

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

**Example 3:**

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

&#x20;

**Constraints:**

* `1 <= s.length <= 105`
* `s` contains only lowercase English letters.

## Intuition

```
Approach 1: Space N, Time N

iteratively delete the count of frequencies in the map,
Till it becomes 0, or we are not able to find in map


Approach 2: Space 1, Time N

Sort according to freq
1 2 2 3 3
Now come from last,
Make second last as 2
The third last one less than second last
So on in array till we reach zero
```

### Links

<https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/description/?envType=daily-question&envId=2023-09-12>

### Video Links

<https://www.youtube.com/watch?v=sq7LBb6Kd3g&ab_channel=AryanMittal>

### Approach 1:

```
Space taken 
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int minDeletions(string s) {
        unordered_map<char,int> freq;
        unordered_map<int,int> count;
        for(auto &c: s)
            freq[c]++;

        for(auto &it: freq)
            count[it.second]++;
        
        int ans=0;
        for(auto &it: count){
            if(it.second == 1)
                continue;

            while(it.second!=1) {
                it.second--;
                int val = it.first;
                int ct = 0;

                while(count.find(val) != count.end()){
                    val--;
                    ct++;
                }

                if(val != 0)
                    count[val]++;

                ans+=ct;
            }
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
Without space
```

{% code title="C++" lineNumbers="true" %}

```cpp
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;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###