Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1647.html
1647. Minimum Deletions to Make Character Frequencies Unique
Level
Medium
Description
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^5
s
contains only lowercase English letters.
Solution
Loop over s
and obtain the count of each letter in s
. Then use a list to store the nonzero counts of the letters, and sort the list. Use a set to store the counts in order to quickly check whether a count already exists. Maintain the current number of counts and loop over the list backwards. If two adjacent elements in the list are the same, then the former element needs to be reduced. Reduce the former elements with minimum times to make all elements unique. Then update the number of diletions, update the current number of counts and add the new count after deletion into the set. Finally, return the number of deletions.

class Solution { public int minDeletions(String s) { int[] counts = new int[26]; int length = s.length(); for (int i = 0; i < length; i++) counts[s.charAt(i)  'a']++; List<Integer> countsList = new ArrayList<Integer>(); Set<Integer> countsSet = new HashSet<Integer>(); for (int i = 0; i < 26; i++) { if (counts[i] > 0) { countsList.add(counts[i]); countsSet.add(counts[i]); } } Collections.sort(countsList); int deletions = 0; int size = countsList.size(); int curCount = countsList.get(size  1); for (int i = size  2; i >= 0; i) { int count = countsList.get(i); if (count == countsList.get(i + 1)) { curCount = Math.min(curCount, count  1); while (curCount > 0 && countsSet.contains(curCount)) curCount; countsSet.add(curCount); deletions += count  curCount; } } return deletions; } }

Todo

class Solution: def minDeletions(self, s: str) > int: cnt = Counter(s) ans, pre = 0, inf for v in sorted(cnt.values(), reverse=True): if pre == 0: ans += v elif v >= pre: ans += v  pre + 1 pre = 1 else: pre = v return ans ############ # 1647. Minimum Deletions to Make Character Frequencies Unique # https://leetcode.com/problems/minimumdeletionstomakecharacterfrequenciesunique/ from heapq import heappop, heappush class Solution: # max heap def minDeletions(self, s: str) > int: c = Counter(s) q = [] for v in c.values(): heappush(q, v) res = 0 while q: freq = heappop(q) freq = freq if not q: return res if freq == q[0]: if freq > 1: v = freq  1 heappush(q, v) res += 1 return res # greedy def minDeletions(self, S: str) > int: c = Counter(S) s = set() res = 0 for v in c.values(): t = v while t in s: res += 1 t = 1 if t != 0: s.add(t) return res