[LeetCode] 1647. Minimum Deletions to Make Character Frequencies Unique

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.

字符频次唯一的最小删除次数。

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 “aab” 中，’a’ 的频次是 2，而 ‘b’ 的频次是 1 。

思路

遍历数组的时候，用一个长度为26的 int[] map 数组记录 input 字符串中每个不同字母的出现次数。

接着我们再创建一个 hashset，去遍历这个长度为 26 的 int 数组，对于当前字母的出现次数 map[i]，如果他在 hashset 中出现过，那么他就不是一个 unique 的出现次数，那么我们就把这个出现次数减一，直到他变成一个 unique 的出现次数，再加入 hashset。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minDeletions(String s) {
        int[] map = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            map[s.charAt(i) - 'a']++;
        }

        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int i = 0; i < map.length; i++) {
            while (map[i] > 0 && set.contains(map[i])) {
                map[i]--;
                count++;
            }
            set.add(map[i]);
        }
        return count;
    }
}