以下是 LeetCode 3389. 使字符频率相等的最少操作次数 的 Java 实现,基于枚举目标频率 + 动态规划的思路:

```java
class Solution {
    public int makeStringGood(String s) {
        // 1. 统计每个字母的出现次数
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        
        // 2. 找到最大频率,作为枚举 target 的上界
        int maxCnt = 0;
        for (int x : cnt) {
            maxCnt = Math.max(maxCnt, x);
        }
        
        // target = 0 时,全部删除,操作次数为 s.length()
        int ans = s.length();
        
        // f[i] 表示从第 i 个字母到 'z',都变成 target 或 0 的最小操作次数
        // 数组大小为 27,f[26] = 0 作为边界(后面没有字母了)
        int[] f = new int[27];
        
        // 3. 枚举目标频率 target
        for (int target = 1; target <= maxCnt; target++) {
            // 从 'z' 开始倒序 DP
            f[25] = Math.min(cnt[25], Math.abs(cnt[25] - target));
            
            for (int i = 24; i >= 0; i--) {
                int x = cnt[i];
                
                // 剪枝:当前字母不出现,无需操作
                if (x == 0) {
                    f[i] = f[i + 1];
                    continue;
                }
                
                // 情况1:单独操作当前字母(变成 target 或 0)
                // 变成 0:删除 x 次
                // 变成 target:添加/删除 abs(x - target) 次
                f[i] = f[i + 1] + Math.min(x, Math.abs(x - target));
                
                // 情况2:与下一个字母联动使用操作三(a->b, b->c 等)
                // 只有当下一个字母需要变大时,操作三才有意义
                int y = cnt[i + 1];
                if (0 < y && y < target) {
                    // t 表示当前字母 x 的目标:要么变成 target,要么变成 0
                    int t = (x > target) ? target : 0;
                    
                    // 操作三:每执行一次,x 减 1,y 加 1
                    // 需要执行 max(x - t, target - y) 次
                    // 因为操作三结束后,可能还需要额外的添加/删除操作
                    int cost = Math.max(x - t, target - y);
                    f[i] = Math.min(f[i], f[i + 2] + cost);
                }
            }
            
            ans = Math.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`,完全在可接受范围内。

 

更多推荐