Kimi LeetCode 3389. 使字符频率相等的最少操作次数 Python3实现
以下是 LeetCode 3389. 使字符频率相等的最少操作次数 的 Python3 实现:
```python
class Solution:
def makeStringGood(self, s: str) -> int:
# 1. 统计每个字母的出现次数
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
max_cnt = max(cnt)
n = len(s)
ans = n # target = 0 时,全部删除
# f[i] 表示从第 i 个字母到 'z' 的最小操作次数
# f[26] = 0 作为边界(后面没有字母了)
f = [0] * 27
# 2. 枚举目标频率 target
for target in range(1, max_cnt + 1):
# 'z' 单独处理(没有下一个字母可以联动)
f[25] = min(cnt[25], abs(cnt[25] - target))
# 从 'y' 倒序到 'a'
for i in range(24, -1, -1):
x = cnt[i]
# 当前字母不出现,直接继承后面的结果
if x == 0:
f[i] = f[i + 1]
continue
# 方案1:单独处理当前字母
# 变成 0:删除 x 次
# 变成 target:添加/删除 abs(x - target) 次
f[i] = f[i + 1] + min(x, abs(x - target))
# 方案2:与下一个字母联动使用操作三(a->b, b->c 等)
# 只有当下一个字母频率不足 target 时,转移才有意义
y = cnt[i + 1]
if 0 < y < target:
# t: 当前字母的目标值
# 若 x > target,保留 target 个,多余部分转移给下一个
# 若 x <= target,全部转移(目标为 0)
t = target if x > target else 0
# 操作三:每执行一次,x 减 1,y 加 1
# 总成本 = max(当前需要减少的量, 下一个字母需要增加的量)
cost = max(x - t, target - y)
f[i] = min(f[i], f[i + 2] + cost)
ans = min(ans, f[0])
return ans
```
思路说明
操作 效果
删除 任意 `cnt[i]` 减 1
添加 任意 `cnt[i]` 加 1
变下一个字母 `cnt[i]` 减 1 且 `cnt[i+1]` 加 1
核心观察:最终"好"字符串中,每种字母要么出现 target 次,要么出现 0 次(被完全删除)。
动态规划:
- 枚举目标频率 `target`(从 1 到最大频率)
- `f[i]` 表示从第 `i` 个字母到 `'z'` 都处理好的最小操作数
- 每个字母有两种选择:
1. 单独处理:变成 `target` 或 `0`
2. 与下一个字母联动:如果下一个字母频率不足 `target`,可以通过"变下一个字母"的操作,把当前字母"转移"一部分给下一个字母,可能更优
复杂度:`O(26 × maxCnt)`,其中 `maxCnt ≤ n ≤ 20000`,完全在可接受范围内。
更多推荐




所有评论(0)