Leetcode 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.
Test Cases
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 <= 105scontains only lowercase English letters.
Approach
Our task is to get rid of the same frequency characters and make good string. So in good string, we will be having characters with different frequencies. Our first basic thing will be to find the frequency of each and every characters present in the string. Since we have only lowercase english letters, we can just make use of an array of size 26.
After getting the frequency, we just just need to get rid of all the characters, one by one so that the frequencies will be different for each and every character. Sorting will be handy here as we can get to know the frequencies in increasing or decreasing order and get to know whether deleting one character makes the string unique or not.
So we have the array with frequency of each and every character in the string. We are not allowed to add a new character so that the frequency increases and still the string may become good. We are only allowed to delete the character and reduce the frequency. We are only concerning about frequency, not about the character and the final string. So just sorting the frequency array will do no harm for us.
Now traverse the frequency array from the back as after sorting we have the largest frequency number there. Store the last frequency as maximum count.If we have the current frequency as 0, just get out from the loop as the array will be sorted and there is no point in looking to left again.
If our current frequency < maximum we have seen so far, just update maximum as current count. If our current frequency > maximum frequency, we can make the deletion. deletionCount += current — max.
If our maximum frequency is > 0, we just reduce it by 1.
Finally return the deletionCount;
Time and Space Complexity
We are traversing through the string at first to store the frequency which is O(N) time complexity. We store the frequency to an array of size 26 and sort that array which makes complexity as O(26 * log(26)) = O(1).
Again we are traversing through the frequency array of size 26 which makes O(26) = O(1) time complexity. So total complexity=O(N).
Space complexity will be O(26) as we only use extra space to store the frequency.
Code
