3389. 使字符频率相等的最少操作次数
来源第 428 场周赛 Q4难度困难分数2940
题目描述
给你一个字符串 s 。
如果字符串 t 中的字符出现次数相等，那么我们称 t 为 好的 。
你可以执行以下操作 任意次 ：
- 从
s中删除一个字符。 - 往
s中添加一个字符。 - 将
s中一个字母变成字母表中下一个字母。
注意 ，第三个操作不能将 'z' 变为 'a' 。
请你返回将 s 变 好 的 最少 操作次数。
示例 1：
输入：s = "acab"
输出：1
解释：
删掉一个字符 'a' ，s 变为好的。
示例 2：
输入：s = "wddw"
输出：0
解释：
s 一开始就是好的，所以不需要执行任何操作。
示例 3：
输入：s = "aaabc"
输出：2
解释：
通过以下操作，将 s 变好：
- 将一个
'a'变为'b'。 - 往
s中插入一个'c'。
提示：
1 <= s.length <= 2 * 104s只包含小写英文字母。
解法
方法一
思考
通过增删改字母使 \(26\) 个频率要么为 \(0\) 要么同为某个 \(t\)。\(|s| \le 2 \times 10^4\)，可枚举目标 \(t\)，再对排序后的频率做分配。
改一个字母等价于从某频次挪到另一频次，增删则单独计价。对每个 \(t\) 用 DP 或贪心把当前频率匹配到「保留 \(t\) 或清零」。
取所有 \(t\) 的最小操作数。\(t\) 不超过最大频率，枚举量可接受。
1 | |
1 | |
1 | |
1 | |