DSA problem
Minimum Deletions to Make Character Frequencies Unique
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.
You may delete any characters; the goal is to reach a state where every character that still appears does so a distinct number of times, using as few deletions as possible.
Examples
Example 1
Input:
s = "aab"Output:
0Explanation: s is already good: "a" has frequency 2 and "b" has frequency 1, which are distinct.
Example 2
Input:
s = "aaabbbcc"Output:
2Explanation: You can delete two "b"s resulting in "aaabcc". Now frequencies are a=3, b=1, c=2, all distinct. It is impossible to do this with fewer deletions.
Example 3
Input:
s = "ceabaacb"Output:
2Explanation: You can delete both "c"s leaving "eabaab" with frequencies a=3, b=2, e=1. There are other ways to delete 2 characters but none with fewer.
Constraints
- 1 <= s.length <= 10^5
- s contains only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.