---

1531. 压缩字符串 II

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 1531. 压缩字符串 II - 力扣

题目大意

描述：给定一个字符串 $s$ 和一个整数 $k$。可以删除 $k$ 个字符。然后对剩余字符进行游程编码（RLE），编码规则：

• 连续 $a$ 个相同字符 $ch$ 编码为 $a + ch$（如 "aaabb" → "3a2b"），但单个字符省略数字（如 "a" → "a"）。

要求：返回删除 $k$ 个字符后，RLE 编码的最小长度。

说明：

• $1 \le s.length \le 100$。
• $0 \le k \le s.length$。
• $s$ 只包含大写字母。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：DP

1. 核心思想

定义 $dp[i][j]$ 表示考虑 $s$ 的前 $i$ 个字符（$0$-based），删除 $j$ 个字符后，RLE 编码的最小长度。

转移时，对于第 $i$ 个字符：

• 删除它：$dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])$。
• 保留它：从 $i$ 开始往前，保留一组连续的相同字符。

保留时的具体计算：对于某个起点 $p$（从 $i$ 向左），统计 $s[p..i]$ 中与 $s[i]$ 相同的字符数 $same$ 和需要删除的不同字符数 $del$。如果 $j + del \le k$：

• $len = rle\_len(same)$（$same$ 个相同字符的编码长度）。
• $dp[i+1][j+del] = min(dp[i+1][j+del], dp[p][j] + len)$。

2. 具体步骤

第 1 步：初始化 $dp$ 为 $inf$，$dp[0][0] = 0$。

第 2 步：遍历 $i = 0 \to n-1$：

• 对于每个 $j = 0 \to k$，如果 $dp[i][j]$ 不是 $inf$：
  • 删除 $s[i]$：$dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])$。
  • 保留 $s[i]$：从 $i$ 向左到 $p$，统计与 $s[i]$ 相同的字符数和要删除的不同字符数。

第 3 步：返回 $min(dp[n][j])$ 对于 $j \le k$。

3. RLE 编码长度

• $same = 1$：长度为 $1$（不加数字）。
• $same \in [2, 9]$：长度为 $2$。
• $same \in [10, 99]$：长度为 $3$。
• $same = 100$：长度为 $4$。

4. 举例说明

以 $s = "aaabcccd", k = 2$ 为例：

考虑保留所有字符：$"a3b1c3d1"$ → RLE 长度 $= 2+2+2+2 = 8$（"a3bc3d"）。不对，"aaabcccd" 的 RLE 是 "3a1b3c1d" → 长度 $= 2+2+2+2 = 8$。

删除 $2$ 个字符：

• 删除 $b$ 和 $d$：$"aaaccc"$ → "3a3c"，长度 $= 2+2 = 4$。
• 或其他方案。

思路 1：代码

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        INF = 10**9
        dp = [[INF] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        def rle_len(x):
            if x == 0:
                return 0
            if x == 1:
                return 1
            if x < 10:
                return 2
            if x < 100:
                return 3
            return 4

        for i in range(1, n + 1):
            for j in range(k + 1):
                if dp[i - 1][j] == INF:
                    continue
                # 删除 s[i-1]
                if j + 1 <= k:
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j])

                # 保留 s[i-1]，统计往前连续的相同字符
                same = 0
                del_cnt = 0
                for p in range(i - 1, -1, -1):
                    if s[p] == s[i - 1]:
                        same += 1
                    else:
                        del_cnt += 1
                    if j + del_cnt > k:
                        break
                    dp[i][j + del_cnt] = min(
                        dp[i][j + del_cnt],
                        dp[p][j] + rle_len(same)
                    )

        return min(dp[n])

思路 1：复杂度分析

• 时间复杂度：$O(n^2 \times k)$，$n \le 100$，可行。
• 空间复杂度：$O(n \times k)$。