# 1647. Minimum Deletions to Make Character Frequencies Unique
## Problem Statement
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`.
**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).
**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
### Video Links
### Approach 1:
```
Space taken
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
int minDeletions(string s) {
unordered_map freq;
unordered_map 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 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
###
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://coding-9.gitbook.io/untitled/hash-and-map/1647.-minimum-deletions-to-make-character-frequencies-unique.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.