题目描述

给你一个字符串 s。

如果字符串 t 中的字符出现次数相等，那么我们称 t 为 好的。

你可以执行以下操作 任意次：

• 从 s 中删除一个字符。
• 往 s 中添加一个字符。
• 将 s 中一个字母变成字母表中下一个字母。

注意，第三个操作不能将 'z' 变为 'a'。

请你返回将 s 变 好 的 最少 操作次数。

样例

输入：s = "acab"

输出：1

解释：

删掉一个字符 'a'，s 变为好的。

输入：s = "wddw"

输出：0

解释：

s 一开始就是好的，所以不需要执行任何操作。

输入：s = "aaabc"

输出：2

解释：

通过以下操作，将 s 变好：

将一个 'a' 变为 'b'。
往 s 中插入一个 'c'。

限制

• 1 <= s.length <= 2 * 10^4
• s 只包含小写英文字母。

算法

(动态规划) $O(n |\Sigma|)$

1. 求出原始字符串中，每个字符的出现次数 $occ(i)$。
2. 假设给定了最终每个字符的出现次数 $target$，则最终 $occ(i) = target$ 或者 $occ(i) = 0$。
3. 注意到，操作一和操作二相当于对某个 $occ(i)$ 减少 $1$ 或增加 $1$。
4. 对于操作三，相当于 $occ(i - 1)$ 减少 $1$ 的同时 $occ(i)$ 增加 $1$。更进一步地，在最优情况下，这个转移不会有连续三个或以上的字符都发生，即 $a \to b \to c$ 是无意义的，完全可以令 $a$ 减 $1$，再令 $c$ 加 $1$。
5. 基于以上判断，可以采用动态规划求解。从 $1$ 到 $n$ 枚举目标值 $target$。
6. 设状态 $f(i)$ 表示 $occ(1)$ 到 $occ(i)$ 都满足条件的最小修改次数。
7. 初始时，$f(0) = 0$，其余待定。
8. 转移时，对于 $f(i)$，可以单独修改 $occ(i)$ 达到目标，即 $f(i) = f(i - 1) + \min(occ(i), |target - occ(i)|)$。
9. 当 $occ(i) < target$ 时，也可以尝试和上一个字符绑定，从上一个字符转移。此时需要判断 $occ(i - 1)$ 与 $target$ 的大小关系：
   1. 若 $occ(i - 1) < target$，则 $f(i) = f(i - 2) + \max(d, occ(i - 1))$，这里 $\max(d, occ(i - 1))$ 是因为当 $d < occ(i - 1)$ 时，需要转移 $d$ 个然后去掉上一个字符串剩余的部分。另一种情况同理。
   2. 若 $occ(i - 1) \ge target$，则 $f(i) = f(i - 2) + \max(d, occ(i - 1) - target)$，即这里相当于把上一个字符的目标定在了 $target$（如果定在 $0$，则从上一个字符给到下一个字符的操作无意义）。
10. 最终用 $f(|\Sigma|)$ 更新答案。

时间复杂度

• 预处理的时间复杂度为 $O(n)$。
• 动态规划的状态数为 $O(|\Sigma|)$，转移时间为常数。
• 动态规划的次数为 $O(n)$。
• 故总时间复杂度为 $O(n |\Sigma|)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储字符的出现次数和动态规划的状态。

C++ 代码

class Solution {
public:
    int makeStringGood(string s) {
        const int n = s.size(), m = 26;
        vector<int> occ(m + 1, 0);

        for (char c : s)
            ++occ[c - 'a' + 1];

        vector<int> f(m + 1);
        int ans = INT_MAX;

        f[0] = 0;
        for (int target = 1; target <= n; target++) {
            f[1] = min(occ[1], abs(target - occ[1]));

            for (int i = 2; i <= m; i++) {
                f[i] = f[i - 1] + min(occ[i], abs(target - occ[i]));

                if (i >= 2 && occ[i] < target) {
                    int d = target - occ[i];
                    if (occ[i - 1] < target)
                        f[i] = min(f[i], f[i - 2] + max(d, occ[i - 1]));
                    else
                        f[i] = min(f[i], f[i - 2] + max(d, occ[i - 1] - target));
                }
            }

            ans = min(ans, f[m]);
        }

        return ans;
    }
};