1647. Minimum Deletions to Make Character Frequencies Unique
2021/7/21 6:05:55
本文主要是介绍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.
class Solution { public int minDeletions(String s) { int[] freq = new int[26]; for(char c : s.toCharArray()) { freq[c - 'a']++; } Arrays.sort(freq); int exp = freq[25]; int res = 0; for(int i = 25; i >= 0; i--) { if(freq[i] == 0) break; if(freq[i] <= exp) exp = freq[i]; else res += freq[i] - exp; if(exp > 0) exp--; } return res; } }
痛心疾首,greedy。
先给frequency排序,然后拿到最高的frequency as expected。
从后往前iterate,比较当前的frequency和expected,如果freq <= exp, upadate the exp as current freq, else 我们就觉得这个freq太大了,得delete,delete freq - exp。然后更新exp--
这篇关于1647. Minimum Deletions to Make Character Frequencies Unique的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升