贪心题目：字符频次唯一的最小删除次数

题目

标题和出处

标题：字符频次唯一的最小删除次数

出处：1647. 字符频次唯一的最小删除次数

难度

5 级

题目描述

要求

如果字符串s \texttt{s}s中不存在两个不同字符频次相同的情况，就称s \texttt{s}s是优质字符串。

给定一个字符串s \texttt{s}s，返回使s \texttt{s}s成为优质字符串需要删除的最小字符数。

字符串中字符的频次是该字符在字符串中的出现次数。例如，在字符串"aab" \texttt{"aab"}"aab"中，‘a’ \texttt{`a'}‘a’的频次是2 \texttt{2}2，‘b’ \texttt{`b'}‘b’的频次是1 \texttt{1}1。

示例

示例 1：

输入：s = "aab" \texttt{s = "aab"}s = "aab"
输出：0 \texttt{0}0
解释：s \texttt{s}s已经是优质字符串。

示例 2：

输入：s = "aaabbbcc" \texttt{s = "aaabbbcc"}s = "aaabbbcc"
输出：2 \texttt{2}2
解释：可以删除两个‘b’ \texttt{`b'}‘b’, 得到优质字符串"aaabcc" \texttt{"aaabcc"}"aaabcc"。
另一种方式是删除一个‘b’ \texttt{`b'}‘b’和一个‘c’ \texttt{`c'}‘c’，得到优质字符串"aaabbc" \texttt{"aaabbc"}"aaabbc"。

示例 3：

输入：s = "ceabaacb" \texttt{s = "ceabaacb"}s = "ceabaacb"
输出：2 \texttt{2}2
解释：可以删除两个‘c’ \texttt{`c'}‘c’得到优质字符串"eabaab" \texttt{"eabaab"}"eabaab"。
注意，只需要关注结果字符串中仍然存在的字符（即忽略频次为0 \texttt{0}0的字符）。

数据范围

• 1 ≤ s.length ≤ 10 5 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{5}1≤s.length≤105
• s \texttt{s}s仅含小写英语字母

解法

思路和算法

优质字符串要求字符串中每个字母的频次各不相同，因此需要首先统计字符串s ss中每个字母的频次，然后计算使字符串s ss成为优质字符串的最小删除次数。

对于x ≥ 1 x \ge 1x≥1，如果存在两个字母的频次都是x xx且没有字母的频次是x − 1 x - 1x−1，则需要将其中一个字母删除一次使频次变成x − 1 x - 1x−1，最小删除次数是1 11。

对于x ≥ k x \ge kx≥k，假设已经存在k kk个字母的频次分别是x xx到x − k + 1 x - k + 1x−k+1的每个整数且没有字母的频次是x − k x - kx−k，如果此时另外有一个字母c cc的频次是x xx，则为了使任意两个字母的频次都不相同，最小删除次数是k kk，理由如下。

• 如果只删除字母c cc，则必须将字母c cc的频次减少到x − k x - kx−k才能使k + 1 k + 1k+1个字母中的任意两个字母的频次都不相同，此时的删除次数是k kk。

• 如果字母c cc的删除次数小于k kk，则字母c cc的频次一定和已经存在的k kk个字母中的一个字母的频次相同，为了使任意两个两个字母的频次都不相同，还需要在已经存在的k kk个字母中删除字母，最后的结果一定是k + 1 k + 1k+1个字母的频次分别是x xx到x − k x - kx−k的每个整数，此时k + 1 k + 1k+1个字母的总删除次数是k kk。

当删除次数是k kk时，可以使k + 1 k + 1k+1个字母中的任意两个字母的频次都不相同。当删除次数小于k kk时，一定存在至少两个字母的频次相同。因此最小删除次数是k kk。

根据上述分析，可以使用贪心的思想计算使字符串s ss成为优质字符串的最小删除次数。

首先统计字符串s ss中每个字母的频次并用哈希表记录，然后遍历哈希表计算最小删除次数，遍历过程中使用一个哈希集合记录已经出现过的频次，对于当前频次x xx，执行如下操作。

1. 如果x xx已经在哈希集合中，则每次将x xx减1 11并将删除次数加1 11，直到x xx变成0 00或x xx不在哈希集合中。

2. 当x > 0 x > 0x>0时，将x xx添加到哈希集合中。

遍历结束之后，即可得到使字符串s ss成为优质字符串的最小删除次数。

实现方面，由于字符串s ss只含小写字母，因此可以使用长度为26 2626的数组代替哈希表记录每个字母的频次。

代码

classSolution{publicintminDeletions(Strings){intdeletions=0;int[]counts=newint[26];intlength=s.length();for(inti=0;i<length;i++){charc=s.charAt(i);counts[c-'a']++;}Set<Integer>set=newHashSet<Integer>();for(inti=0;i<26;i++){while(counts[i]>0&&!set.add(counts[i])){counts[i]--;deletions++;}}returndeletions;}}

复杂度分析

• 时间复杂度：O ( n + ∣ Σ ∣ ) O(n + |\Sigma|)O(n+∣Σ∣)，其中n nn是字符串s ss的长度，Σ \SigmaΣ是字符集，这道题中Σ \SigmaΣ是全部小写英语字母，∣ Σ ∣ = 26 |\Sigma| = 26∣Σ∣=26。需要遍历字符串一次统计每个字母的频次，然后遍历每个字母的频次计算最小删除次数。

• 空间复杂度：O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)，其中Σ \SigmaΣ是字符集，这道题中Σ \SigmaΣ是全部小写英语字母，∣ Σ ∣ = 26 |\Sigma| = 26∣Σ∣=26。空间复杂度主要取决于哈希表，需要使用哈希表记录每个字母的频次。