文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题字符频次唯一的最小删除次数出处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≤105s \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−k1的每个整数且没有字母的频次是x − k x - kx−k如果此时另外有一个字母c cc的频次是x xx则为了使任意两个字母的频次都不相同最小删除次数是k kk理由如下。如果只删除字母c cc则必须将字母c cc的频次减少到x − k x - kx−k才能使k 1 k 1k1个字母中的任意两个字母的频次都不相同此时的删除次数是k kk。如果字母c cc的删除次数小于k kk则字母c cc的频次一定和已经存在的k kk个字母中的一个字母的频次相同为了使任意两个两个字母的频次都不相同还需要在已经存在的k kk个字母中删除字母最后的结果一定是k 1 k 1k1个字母的频次分别是x xx到x − k x - kx−k的每个整数此时k 1 k 1k1个字母的总删除次数是k kk。当删除次数是k kk时可以使k 1 k 1k1个字母中的任意两个字母的频次都不相同。当删除次数小于k kk时一定存在至少两个字母的频次相同。因此最小删除次数是k kk。根据上述分析可以使用贪心的思想计算使字符串s ss成为优质字符串的最小删除次数。首先统计字符串s ss中每个字母的频次并用哈希表记录然后遍历哈希表计算最小删除次数遍历过程中使用一个哈希集合记录已经出现过的频次对于当前频次x xx执行如下操作。如果x xx已经在哈希集合中则每次将x xx减1 11并将删除次数加1 11直到x xx变成0 00或x xx不在哈希集合中。当x 0 x 0x0时将x xx添加到哈希集合中。遍历结束之后即可得到使字符串s ss成为优质字符串的最小删除次数。实现方面由于字符串s ss只含小写字母因此可以使用长度为26 2626的数组代替哈希表记录每个字母的频次。代码classSolution{publicintminDeletions(Strings){intdeletions0;int[]countsnewint[26];intlengths.length();for(inti0;ilength;i){charcs.charAt(i);counts[c-a];}SetIntegersetnewHashSetInteger();for(inti0;i26;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。空间复杂度主要取决于哈希表需要使用哈希表记录每个字母的频次。