1647. Minimum Deletions to Make Character Frequencies Unique #

Problem #

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.

Problem Summary #

If in the string s there are no two different characters with the same frequency, then s is called a good string.

Given a string s, return the minimum number of characters that need to be deleted to make s a good string.

The frequency of a character in a string is the number of times that character appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.

Constraints:

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

Solution Approach #

• Given a string s, output the minimum number of characters that need to be deleted to make s a “good string”. The definition of a “good string” is: there are no two different characters in string s with the same frequency.
• First count the frequencies of the 26 letters in the string, then sort the frequencies in descending order. Starting from the larger frequencies, adjust them one by one: for example, suppose the previous frequency and the next frequency are equal; delete one occurrence of the previous character, decrement its frequency by one, and sort again. If the frequencies are still equal, continue adjusting. If the frequencies become different, move the cursor backward and continue adjusting the subsequent frequencies. When all frequencies are different, the final result can be output.
• Pay attention to the case where the frequency is 0, which means all occurrences of that letter have been deleted. Once the frequency becomes 0, it no longer needs to be compared.

Code #

package leetcode

import (
	"sort"
)

func minDeletions(s string) int {
	frequency, res := make([]int, 26), 0
	for i := 0; i < len(s); i++ {
		frequency[s[i]-'a']++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(frequency)))
	for i := 1; i <= 25; i++ {
		if frequency[i] == frequency[i-1] && frequency[i] != 0 {
			res++
			frequency[i]--
			sort.Sort(sort.Reverse(sort.IntSlice(frequency)))
			i--
		}
	}
	return res
}