LeetCode 1531. 压缩字符串 II【动态规划】2575

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

---

解法 动态规划+字符串

称给定字符串 $s$ 为「原串」，压缩后字符串 $t$ 为「压串」。目标是从 $s$ 中删除至多 $k$ 个字符，使其对应的 $t$ 长度最小。

压串 $t$ 由字母和数字间隔组成，$c_x$ 表示字母，$d_x$ 表示次数，$(c_x,d_x)$ 表示原串 $s$ 中连续出现了 $d_x$ 次字母 $c_x$ 。当出现次数为 $1$ 时，我们省略 $d_x$ ：
$$t=c_1{d}_1{c}_2{d}_2\dots c_m{d}_m$$
我们可以根据 $t$ 的形式进行动态规划。在状态转移的过程中，每一次只处理 $t$ 中一个二元组 $(c_x,d_x)$ 。

我们用 $f[i][j]$ 表示对于原串 $s$ 的前 $i$ 个字符，通过删除其中的 $j$ 个字符，剩余的 $i?j$ 个字符可以得到的最小的压串的长度。为了对边界条件进行处理，这里的 $i$ 和 $j$ 都从 $1$ 开始编号。$i$ 的最大值为 $|s|$（原串的长度），$j$ 的最大值为 $k$ 。

• 动态规划的边界条件为 $f[0][0]=0$ ，表示空串对应的压串长度为 $0$ 。由于要求的是 $f[i][j]$ 的最小值，所以先把它们的值初始化为一个很大的正整数。
• 最终答案即为 $f[n][0\dots k]$ 中的最小值，即我们可以从 $s$ 中删除至多 $k$ 个字符。由于删除一个字符（得到的压串的长度）永远不会劣于保留该字符，因此实际上最终的答案就是 $f[n][k]$ ，即我们恰好删除 $k$ 个字符。
• 注意：这里的状态表示中，我们不关心到底删除了哪 $j$ 个字符。

如何进行状态转移呢？我们可以考虑是否删除第 $i$ 个字符。

• 如果第 $i$ 个字符被删除，则前 $i?1$ 个字符中就要删除 $j?1$ 个字符，状态转移方程为：$$f[i][j]=f[i?1][j?1]$$

• 如果第 $i$ 个字符没有被删除，那么考虑以该字符 $s[i]$ 结尾的一个 $(c_x,d_x)$ 二元组，其中 $c_x=s[i]$ 。我们要在 $[1,i)$ 的范围内再选择若干个（包括零个）与 $s[i]$ 相同的字符（即保留一个、两个…… $d_x$ 个 $c_x$），一起进行压缩。在选择范围内与 $s[i]$ 不同的字符，全部被删除。通俗来说，如果保留字符 $c_x$ ，则此时往前尽量选择保留与字符 $c_x$ 相同的字符。这个状态转移确实不好理解，但仔细思考一下，最优解应该是包含在里面的。

  形式化地说，我们选择了位置：$$p_1<p_2<?<p_{d_x?1}<i$$ 其中 $$s[p_1]=s[p_2]=?=s[p_{d_x?1}]=s[i]=c_x$$
  那么我们选择的范围为 $[p_1,i]$ ，在其中选择了 $d_x$ 个字符 $c_x$ ，剩余的 $i?p_1+1?d_x$ 个字符（无论是否为 $c_x$）都必须被删除。那么前 $p_1?1$ 个字符中就有 $j?(i?p_1+1?d_x)$ 个字符被删除，状态转移方程为： f [ i ] [ j ] = min ? X d { f [ p 1 ? 1 ] [ j ? ( i ? p 1 + 1 ? d x ) ] + c o s t ( d x ) } f[i][j]= \min_{ X_d } \{ f[p_1 - 1][j - (i - p_1 + 1 - d_x)] + cost(d_x) \} f[i][j]=Xd?min?{f[p1??1][j?(i?p1?+1?dx?)]+cost(dx?)}
  其中 $X_d$ 表示「包含了所有选择 $p_1,\dots ,p_{d_x?1}$ 的方案集合?」，$cost(d_x)$ 表示压缩 $d_x$ 个字符得到的长度：$$cost(d_x)=?\begin{array}{ll}1,& d_x=1\\ 2,& 2\le d_x\le 9\\ 3,& 10\le d_x\le 99\\ 4,& d_x=100\end{array}$$
  实际上，上述状态转移方程的复杂度非常高，因为 $X_d$ 是一个非常大的集合，我们枚举每一种方案是不现实的。

事实上，如果 $p_1,\dots ,p_{d_x?1},i$ 是原串 $s$ 中连续的出现字符 $c_x$ 的位置（不看其他字符），那么方案数就没有这么多了。我们只需要枚举 $d_x$ ，就可以从 $i$ 开始向左依次选取出现字符 $c_x$ 的位置，当选取了 $d_x?1$ 次后（即保留 $d_x$ 个 $c_x$），就对应着唯一的 $p_1,\dots ,p_{d_x?1},i$ 。那么这样只考虑选择连续的 $c_x$ 的做法是否正确呢？

例如 $s[\mathrm{1...}i]=aabca$ 时，我们要选择 $2$ 个 $a$ ，其中一个 $a$ 是 $s[i]$ ，我们如何保证只考虑选择连续的 $a$ ，即选择 $a\underline{a}bc\underline{a}$ ，而不考虑 $\underline{a}abc\underline{a}$ 这种情况（中间隔了一个 $a$ ）呢？

可以发现，在 $\underline{a}abc\underline{a}$ 这种情况中，我们保留了 $2$ 个 $a$ 而删除了 $3$ 个字符。由于删除任意一个字符的代价都是一样的，因此我们不如从左往右连续地保留 $2$ 个出现的 $a$ ，而删除剩余的 $3$ 个字符，即 $\underline{a}\underline{a}bca$ ，这两种情况是等价的。而后者在 $s[\mathrm{1...}{i}^{\prime }]=s[\mathrm{1...2}]=aa$ 时就已经被考虑到，因此我们不用考虑前者。

更直观地说，如果我们选择的 $d_x$ 个 $c_x$ 不是连续的，那么我们可以在对应的选择范围内从左到右连续地重新选择 $d_x$ 个 $c_x$ ，二者是等价的。而后者由于连续性，会在之前的状态转移中被考虑到。

因此，我们可对状态转移方程进行优化，只考虑选择连续的 $c_x$ ：
f [ i ] [ j ] = min ? s [ i 0 ] = s [ i ] { f [ i 0 ? 1 ] [ j ? d i f f ( i 0 , i ) ] + c o s t ( s a m e ( i 0 , i ) ) } f[i][j] = \min_{ s[i_0] = s[i] } \{ f[i_0 - 1][j - diff(i_0, i) ] + cost(same(i_0, i))\} f[i][j]=s[i0?]=s[i]min?{f[i0??1][j?diff(i0?,i)]+cost(same(i0?,i))}
其中 $diff(i_0,i)$ 表示 $s[i_0\dots i]$ 中与 $s[i]$ 不同字符数目，$same(i_0,i)$ 表示 $s[i_0\dots i]$ 中与 $s[i]$ 相同的字符数目，有：
$$diff(i_0,i)+same(i_0,i)=i?i_0+1$$
也就是说，我们枚举满足 $s[i_0]=s[i]=c_x$ 的 $i_0$ ，选择所有在 $[i_0,i]$ 范围内的 $c_x$ ，删除剩余的字符（此时剩余的字符均不会是 $c_x$）。

// cpp
class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        auto calc = [](int x) {
            if (x == 1) return 1;
            if (x < 10) return 2;
            if (x < 100) return 3;
            return 4;
        };
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX >> 1));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k && j <= i; ++j) { // 删除j个字符
                // 删除0个字符时要保留s[i-1]
                // 删除多个字符时考虑删除第i个字符和不删除第i个字符的情况
                if (j > 0) f[i][j] = f[i - 1][j - 1]; // 删除s[i-1]这个字符
                int same = 0, diff = 0; // diff统计不同的字符,都是要删除的
                for (int i0 = i; i0 >= 1 && diff <= j; --i0) { // diff<=j
                    if (s[i0 - 1] == s[i - 1]) {
                        ++same; // 删除[i0-1,i-1]中间的不同字符
                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same));
                    } else {
                        ++diff;
                    }
                }
            }
        }
        return f[n][k];
    }
};

// java
class Solution {
    private int calc(int x) {
        if (x == 1) return 1;
        if (x < 10) return 2;
        if (x < 100) return 3;
        return 4;
    }
    public int getLengthOfOptimalCompression(String s, int k) {
        int n = s.length();
        int[][] f = new int[n + 1][k + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(f[i], Integer.MAX_VALUE >> 1);
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k && j <= i; ++j) {
                if (j > 0) f[i][j] = f[i - 1][j - 1];
                int same = 0, diff = 0;
                for (int i0 = i; i0 >= 1 && diff <= j; --i0) {
                    if (s.charAt(i0 - 1) == s.charAt(i - 1)) {
                        ++same;
                        f[i][j] = Math.min(f[i][j], f[i0 - 1][j - diff] + calc(same));
                    } else ++diff;
                }
            }
        }
        return f[n][k];
    }
}

// python
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        calc = lambda x : 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))

        n = len(s)
        f = [ [10**9] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0

        for i in range(1, n + 1):
            for j in range(min(k, i) + 1):
                if j > 0:
                    f[i][j] = f[i - 1][j - 1]
                same = diff = 0
                for i0 in range(i, 0, -1):
                    if s[i0 - 1] == s[i - 1]:
                        same += 1
                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))
                    else:
                        diff += 1
                        if diff > j:
                            break
        return f[n][k]

复杂度分析：

• 时间复杂度：$O(|s{|}^{2}k)$ ，其中 $|s|$ 是原串 $s$ 的长度。动态规划中状态的数目为 $O(|s|k)$ ，每一个状态需要 $O(|s|)$ 的时间进行转移，相乘即可得到总时间复杂度。
• 空间复杂度：$O(|s|k)$ ，即为动态规划中状态的数目。