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;
    }
}

All Problems

All Solutions