Kimi 思考 LeetCode 3389. 使字符频率相等的最少操作次数 Java实现

以下是 LeetCode 3389. 使字符频率相等的最少操作次数 的 Java 实现基于枚举目标频率 动态规划的思路javaclass 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 的最小操作次数// 数组大小为 27f[26] 0 作为边界后面没有字母了int[] f new int[27];// 3. 枚举目标频率 targetfor (int target 1; target maxCnt; target) {// 从 z 开始倒序 DPf[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要么变成 0int t (x target) ? target : 0;// 操作三每执行一次x 减 1y 加 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[i1] 加 1核心观察最终好字符串中每种字母要么出现 target 次要么出现 0 次被完全删除。动态规划- 枚举目标频率 target从 1 到最大频率- f[i] 表示从第 i 个字母到 z 都处理好的最小操作数- 每个字母有两种选择1. 单独处理变成 target 或 02. 与下一个字母联动如果下一个字母频率不足 target可以通过变下一个字母的操作把当前字母转移一部分给下一个字母可能更优复杂度O(26 × maxCnt)其中 maxCnt ≤ n ≤ 20000完全在可接受范围内。