题目描述

行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 "aabccc"，将 "aa" 替换为 "a2"，"ccc" 替换为 "c3"。因此压缩后的字符串变为 "a2bc3"。

注意，本问题中，压缩时没有在单个字符后附加计数 '1'。

给定一个字符串 s 和一个整数 k。你需要从字符串 s 中删除 最多 k 个字符，以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后，s 行程长度编码的最小长度。

样例

输入：s = "aaabcccd", k = 2
输出：4
解释：在不删除任何内容的情况下，压缩后的字符串是 "a3bc3d"，长度为 6。
最优的方案是删除 'b' 和 'd'，这样一来，压缩后的字符串为 "a3c3"，长度是 4。

输入：s = "aabbaa", k = 2
输出：2
解释：如果删去两个 'b' 字符，那么压缩后的字符串是长度为 2 的 "a4"。

输入：s = "aaaaaaaaaaa", k = 0
输出：3
解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 "a11" ，长度为 3。

限制

• 1 <= s.length <= 100
• 0 <= k <= s.length
• s 仅包含小写英文字母。

算法1

(动态规划) $O(26n^2k)$

1. 设状态 $f(i, j, l, c)$ 表示编码了前 $i$ 个字符，删除了 $j$ 个字符，且结尾由 $l$ 个字符 $c$ 组成时的最短编码距离。假设字符串的有效下标从 1 开始。
2. 初始时，$f(0, 0, 0, c) = 0$，表示在没有任何字符时，编码长度为 0。其余状态都为正无穷。
3. 转移时，分为两种情况：
   • 如果 $j > 0$，则我们可以将当前字符删除，所以可以直接转移 $f(i, j, l, c) = \min(f(i, j, l, c), f(i - 1, j - 1, l, c))$。
   • 如果选择不删除当前字符，则又有两种情况：
     • 如果当前字符 $ch$ 和上一次结尾的字符 $c$ 相同，则我们可以接在 $c$ 后边，此时要求 $l > 1$。如果 $l$ 为 $2$，$10$ 或 $100$ 时，转移时需要额外延长加 1。
     • 否则，我们只能以 $ch$ 结尾，转移 $f(i, j, 1, ch) = \min(f(i, j, 1, ch), f(i - 1, j, l, c) + 1)$。
4. 最终答案为 $\min(f(n, j, l, c))$。需要枚举 $j, l, c$ 找到最小值。
5. 优化：
   • 空间上需要开滚动数组，否则会栈溢出（函数内不支持特别大的静态数组声明）
   • 时间上，需要严格控制循环变量的范围；需要将系统自带的 min 函数替换为三目运算符（系统自带的 min 特别慢）。

时间复杂度

• 状态数为 $O(26n^2k)$，每次转移仅需要常数时间，故总时间复杂度为 $O(26n^2k)$。

空间复杂度

• 滚动数组优化后，需要 $O(26nk)$ 的空间。

C++ 代码

#define min(x, y) ((x) < (y) ? (x) : (y))

class Solution {
private:
    static const int N = 110, INF = 1000000000;

public:
    int getLengthOfOptimalCompression(string s, int k) {
        const int n = s.size();

        int f[2][N][N][26];
        memset(f[0], 0x3f, sizeof(f[0]));

        for (int c = 0; c < 26; c++)
            f[0][0][0][c] = 0;

        for (int i = 1; i <= n; i++) {
            memset(f[i & 1], 0x3f, sizeof(f[i & 1]));
            for (int j = 0; j <= min(i, k); j++)
                for (int l = 0; l <= i - j; l++)
                    for (int c = 0; c < 26; c++) {
                        int &st = f[i & 1][j][l][c];

                        if (j > 0)
                            st = min(st, f[(i - 1) & 1][j - 1][l][c]);

                        int ch = s[i - 1] - 'a';
                        if (l > 1 && ch == c) {
                            if (l == 2 || l == 10 || l == 100)
                                st = min(st, f[(i - 1) & 1][j][l - 1][c] + 1);
                            else
                                st = min(st, f[(i - 1) & 1][j][l - 1][c]);
                        } else {
                            f[i & 1][j][1][ch] = min(
                                f[i & 1][j][1][ch],
                                f[(i - 1) & 1][j][l][c] + 1
                            );
                        }
                    }
        }

        int ans = INF;
        for (int j = 0; j <= k; j++)
            for (int l = 0; l <= n; l++)
                for (int c = 0; c < 26; c++)
                    ans = min(ans, f[n & 1][j][l][c]);

        return ans;
    }
};

算法2

(动态规划) $O(n^2k)$

1. 设状态 $f(i, j)$ 表示考虑了前 $i$ 个字符，删除 $j$ 个字符后的最短编码距离。假设字符串的有效下标从 1 开始。
2. 初始时，$f(0, 0) = 0$，其余为正无穷。
3. 转移时，假设当前字符为 $c$，则有两种选择：
   • 如果 $j > 0$，则我们将当前字符 $c$ 删除，所以可以直接转移 $f(i, j) = \min(f(i, j), f(i - 1, j - 1))$。
   • 如果决定保留当前字符，则我们倒序枚举 $i$ 及其之前所有的位置 $l$，枚举的过程中记录等于 $c$ 的个数 $x$ 和不等于当前字符的个数 $y$。如果发现 $j \ge y$，则可以转移 $f(i, j) = \min(f(i, j), f(i - 1, j - y) + calc(x))$，含义是区间 [l, i] 中，我们删除了所有不等于 $c$ 的字符，然后进行转移，也就是让全为 $c$ 的字符串尽可能长。
4. 最终答案为 $\min(f(n, j))$，从 $0 \le j \le k$ 中找到最小值，但显然删除的字母越多最后的编码越短，所以可以直接取 $f(n, k)$ 作为答案。

时间复杂度

• 状态数为 $O(nk)$，转移时间为 $O(n)$，故总时间复杂度为 $O(n^2k)$。

空间复杂度

• 需要 $O(nk)$ 的空间存储状态。

C++ 代码

#define min(x, y) ((x) < (y) ? (x) : (y))

class Solution {
private:
    inline int calc(int x) {
        if (x >= 100) return 4;
        if (x >= 10) return 3;
        if (x >= 2) return 2;
        return 1;
    }

public:
    int getLengthOfOptimalCompression(string s, int k) {
        const int n = s.size(), INF = 1000000000;
        vector<vector<int>> f(n + 1, vector<int>(k + 1, INF));

        f[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= min(i, k); j++) {
                if (j > 0)
                    f[i][j] = min(f[i][j], f[i - 1][j - 1]);

                int x = 0, y = 0;
                for (int l = i; l >= 1; l--) {
                    if (s[l - 1] == s[i - 1]) x++;
                    else y++;
                    if (j >= y)
                        f[i][j] = min(f[i][j], f[l - 1][j - y] + calc(x));
                }
            }

        return f[n][k];
    }
};