以下是 LeetCode 3389. 使字符频率相等的最少操作次数 的 Rust 实现:

```rust
impl Solution {
    pub fn make_string_good(s: String) -> i32 {
        // 1. 统计每个字母的出现次数
        let mut cnt = [0; 26];
        for ch in s.bytes() {
            cnt[(ch - b'a') as usize] += 1;
        }

        let max_cnt = *cnt.iter().max().unwrap();
        let n = s.len() as i32;
        let mut ans = n; // target = 0 时,全部删除

        // f[i] 表示从第 i 个字母到 'z' 的最小操作次数
        // f[26] = 0 作为边界(后面没有字母了)
        let mut f = [0; 27];

        // 2. 枚举目标频率 target
        for target in 1..=max_cnt {
            // 'z' 单独处理(没有下一个字母可以联动)
            f[25] = cnt[25].min((cnt[25] as i32 - target as i32).abs()) as i32;

            // 从 'y' 倒序到 'a'
            for i in (0..25).rev() {
                let x = cnt[i];

                // 当前字母不出现,直接继承后面的结果
                if x == 0 {
                    f[i] = f[i + 1];
                    continue;
                }

                // 方案1:单独处理当前字母
                // 变成 0:删除 x 次
                // 变成 target:添加/删除 abs(x - target) 次
                f[i] = f[i + 1] + (x as i32).min((x as i32 - target as i32).abs());

                // 方案2:与下一个字母联动使用操作三(a->b, b->c 等)
                // 只有当下一个字母频率不足 target 时,转移才有意义
                let y = cnt[i + 1];
                if 0 < y && y < target {
                    // t: 当前字母的目标值
                    // 若 x > target,保留 target 个,多余部分转移给下一个
                    // 若 x <= target,全部转移(目标为 0)
                    let t = if x > target { target } else { 0 };

                    // 操作三:每执行一次,x 减 1,y 加 1
                    // 总成本 = max(当前需要减少的量, 下一个字母需要增加的量)
                    let cost = (x - t).max(target - y) as i32;
                    f[i] = f[i].min(f[i + 2] + cost);
                }
            }

            ans = ans.min(f[0]);
        }

        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`,完全在可接受范围内。

 

更多推荐