LeetCode 1647 Minimum Deletions to Make Character Frequencies Unique

LeetCode

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 <= 10<sup>5</sup> s contains only lowercase English letters.

题目大意：

给定一个字符串，求最小删除次数使得字符串的每一种字符频率不同

解题思路：

按题意求解，若遇到频率相同的字符，就将其减一，也就是删除一个字符，使得它不再与其他字符频率相同直到0. 关键在用一个unique_count的set来记录频数

解题步骤：

N/A

注意事项：

用一个unique_count的set来记录频数

Python代码：

def minDeletions(self, s: str) -> int:
	char_to_count = collections.Counter(s)
	unique_count = set()
	res = 0
	for char, count in char_to_count.items():
		cur_count = count
		while cur_count in unique_count:
			cur_count -= 1
			res += 1
		if cur_count > 0:
			unique_count.add(cur_count)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)