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 non-zero 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/minimum-deletions-to-make-character-frequencies-unique/

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

All Problems

All Solutions