字符串压缩 II（LeetCode 1531）全解：有限删除预算下的最优游程编码压缩，三种动态规划思路与 10 语言实现

字符串压缩 II（LeetCode 1531）全解：有限删除预算下的最优游程编码压缩，三种动态规划思路与 10 语言实现

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南围绕 LeetCode 1531「字符串压缩 II」（String Compression II）展开：给定一个字符串s，允许删除最多k个字符，目标是让删除后字符串的游程编码（Run-Length Encoding）长度最小。文章完整覆盖了自顶向下 4 维记忆化搜索、自顶向下 2 维优化版、自底向上迭代 DP 三种解法，并结合本仓库 articles/string-compression-ii.md 的 10 语言题解与 java/1531-string-compression-ii.java、kotlin/1531-string-compression-ii.kt 源码实现，帮你彻底吃透这一道「DP 状态设计 + 压缩长度阈值」结合的经典难题。

前置知识

在动手解题前，需要先掌握以下四块基础：

• 动态规划（记忆化搜索）：本题需要缓存由「位置、剩余删除次数、前一个字符、前一个字符连续出现次数」共同定义的状态；
• 游程编码（Run-Length Encoding）：理解连续相同字符如何被压缩，例如"aaa"会被压缩成"a3"；
• 多维状态管理：需要同时追踪位置i、删除预算k、前驱字符prev及其连续计数prev_cnt；
• 优化阈值：认识到编码长度只在特定计数（1、9、99）处增加，这是全题最关键的性质。

关于游程编码的基础知识，可以同时参考仓库中的 articles/string-compression.md（经典 String Compression）与 articles/string-encode-and-decode.md（编码与解码）两篇关联文章，理解两者的差异。

问题定义：RLE 长度如何计算

先明确游程编码的长度规律。单个字符本身的编码长度为1，例如"a"；当连续出现2~9次时变为"a5"这种形式，长度为2；10~99次时为"a12"，长度为3；100次时为"a100"，长度为4。

可以看到，编码长度并不是随计数线性增长的，它只在计数越过1、9、99这三个阈值时各增加1。这正是动态规划递推时可以精确计算增量（incr）的根本依据：prev_cnt == 1 || prev_cnt == 9 || prev_cnt == 99时incr = 1，否则incr = 0。

本题就是在这个长度规则之上，允许删除至多k个字符，求删除后字符串 RLE 长度的最小值。

解法一：自顶向下动态规划（4 维状态，朴素版）

直觉

我们希望删除最多k个字符，使游程编码长度最小。核心观察是：编码长度只在1、9、99三个阈值处增加（从 1 到 2 增加一位数字，从 9 到 10 增加一位，从 99 到 100 再增加一位）。使用带记忆化的递归，追踪当前下标、剩余删除次数、前驱字符及其计数。每一步要么延续当前 run（当前字符与前驱相同），要么开启新 run（保留或删除当前字符）。

算法步骤

1. 定义count(i, k, prev, prev_cnt)：i为当前下标，k为剩余删除次数，prev为前一个字符，prev_cnt为该字符已连续出现的次数。
2. 边界情况：若k < 0，返回无穷大（非法）；若i == n，返回0。
3. 若s[i] == prev，延续当前 run：仅当prev_cnt为1、9、99时结果加1（编码长度增长的阈值点）。
4. 若s[i] != prev，取两种选择的最小值：删除s[i]（消耗一次删除机会），或保留s[i]（开启新 run，长度贡献1）。
5. 使用 4 维缓存做记忆化。
6. 返回count(0, k, "", 0)。

Python 实现

class Solution: def getLengthOfOptimalCompression(self, s: str, k: int) -> int: cache = {} def count(i, k, prev, prev_cnt): if (i, k, prev, prev_cnt) in cache: return cache[(i, k, prev, prev_cnt)] if k < 0: return float("inf") if i == len(s): return 0 if s[i] == prev: incr = 1 if prev_cnt in [1, 9, 99] else 0 res = incr + count(i + 1, k, prev, prev_cnt + 1) else: res = min( count(i + 1, k - 1, prev, prev_cnt), # delete s[i] 1 + count(i + 1, k, s[i], 1) # don't delete ) cache[(i, k, prev, prev_cnt)] = res return res return count(0, k, "", 0)

仓库源码对照：Java 与 Kotlin 实现

仓库中的 java/1531-string-compression-ii.java 正是这一朴素版思路，只是把状态拼接成字符串作为HashMap的键：

class Solution { Map<String, Integer> cache; public int getLengthOfOptimalCompression(String s, int k) { cache = new HashMap<>(); return count(0, k, '\0', 0, s); } private int count(int i, int k, char prev, int prev_count, String s){ String curr_state = i + "," + k + "," + prev + "," + prev_count; if(cache.containsKey(curr_state)) return cache.get(curr_state); if(k < 0) return Integer.MAX_VALUE; if(i == s.length()) return 0; int res = -1; if(s.charAt(i) == prev){ int incr = (prev_count == 1 || prev_count == 9 || prev_count == 99)? 1: 0; res = incr + count(i + 1, k, prev, prev_count + 1, s); } else{ res = Math.min(count(i + 1, k - 1, prev, prev_count, s), 1 + count(i + 1, k, s.charAt(i), 1, s)); } cache.put(curr_state, res); return res; } }

Kotlin 版本 的结构完全相同，同样以HashMap<String, Int>缓存、用'Z'作为哨兵前驱字符：

class Solution { fun getLengthOfOptimalCompression(s: String, k: Int): Int { val cache = HashMap<String, Int>() fun count(i: Int, k: Int, prev: Char, prevCount: Int): Int { cache["$i:$k:$prev:$prevCount"]?.let { return it } if (k < 0) return Integer.MAX_VALUE if (i == s.length) return 0 var res = -1 if (s[i] == prev) { val incr = if (prevCount in setOf(1, 9, 99)) 1 else 0 res = incr + count(i + 1, k, s[i], prevCount + 1) } else { res = minOf( count(i + 1, k - 1, prev, prevCount), 1 + count(i + 1, k, s[i], 1) ) } cache["$i:$k:$prev:$prevCount"] = res return res } return count(0, k, 'Z', 0) } }

C++ 实现（4 维数组缓存）

在 C++ 中更高效的做法是直接用 4 维数组缓存，其中prev用0~25表示 26 个小写字母、26作为哨兵（表示"无前驱字符"），prevCnt维度开到101（字符最多 100 次连续出现）：

class Solution { static const int INF = INT_MAX / 2; vector<vector<vector<vector<int>>>> dp; int count(int i, int k, int prev, int prevCnt, string& s) { if (k < 0) return INF; if (i == s.size()) return 0; if (dp[i][k][prev][prevCnt] != -1) return dp[i][k][prev][prevCnt]; int res; if (prev == s[i] - 'a') { int incr = (prevCnt == 1 || prevCnt == 9 || prevCnt == 99) ? 1 : 0; res = incr + count(i + 1, k, prev, prevCnt + 1, s); } else { res = 1 + count(i + 1, k, s[i] - 'a', 1, s); // don't delete if (k > 0) { res = min(res, count(i + 1, k - 1, prev, prevCnt, s)); // delete s[i] } } return dp[i][k][prev][prevCnt] = res; } public: int getLengthOfOptimalCompression(string s, int k) { int n = s.size(); dp = vector<vector<vector<vector<int>>>>( n + 1, vector<vector<vector<int>>>(k + 1, vector<vector<int>>(27, vector<int>(101, -1))) ); return count(0, k, 26, 0, s); } };

JavaScript、C#、Go、Swift、Rust 版本与上述结构完全一致（JavaScript/Go 用字符串键拼接做哈希缓存，Swift/Rust 用多维数组），均收录于原文章 articles/string-compression-ii.md 的多语言标签页中。

时间复杂度与空间复杂度

• 时间复杂度：$O(k \cdot n^2)$
• 空间复杂度：$O(k \cdot n^2)$

其中 $n$ 是字符串 $s$ 的长度，$k$ 是允许删除的最大字符数。

解法二：自顶向下动态规划（2 维状态，优化版）

直觉

不再显式追踪前驱字符及其计数，而是换一种思考方式：在每个位置决定删除当前字符，或让当前字符成为一个新 run 的开头。若开启新 run，则向前扫描，在删除预算内尽量保留匹配字符、删除不匹配字符来扩展这个 run。这样状态空间被压缩到只剩「位置 + 剩余删除次数」两个维度。

算法步骤

1. 定义dfs(i, k)：i为当前下标，k为剩余删除预算。
2. 边界情况：若n - i <= k，说明剩余字符可以全部删掉，返回0。
3. 选项一：若k > 0，删除s[i]，得到dfs(i + 1, k - 1)。
4. 选项二：以s[i]开启一个 run。向前扫描，统计匹配字符数、删除不匹配字符数。实时维护压缩长度comp_len（在计数为1、9、99时增加）。对每个扫描终点，计算comp_len + dfs(j + 1, k - delCnt)。
5. 取所有选项的最小值。
6. 用 2 维缓存dp[n][k+1]记忆化。
7. 返回dfs(0, k)。

Python 实现

class Solution: def getLengthOfOptimalCompression(self, s: str, k: int) -> int: n = len(s) dp = {} def dfs(i, k): if n - i <= k: return 0 if (i, k) in dp: return dp[(i, k)] res = 150 if k > 0: res = dfs(i + 1, k - 1) freq = delCnt = 0 comp_len = 1 for j in range(i, n): if s[i] == s[j]: if freq in [1, 9, 99]: comp_len += 1 freq += 1 else: delCnt += 1 if delCnt > k: break res = min(res, comp_len + dfs(j + 1, k - delCnt)) dp[(i, k)] = res return res return dfs(0, k)

Java 与 C++ 实现

public class Solution { private int n; private int[][] dp; public int getLengthOfOptimalCompression(String s, int k) { n = s.length(); dp = new int[n + 1][k + 1]; for (int[] row : dp) Arrays.fill(row, -1); return dfs(0, k, s); } private int dfs(int i, int k, String s) { if (n - i <= k) return 0; if (dp[i][k] != -1) return dp[i][k]; int res = 150; if (k > 0) res = dfs(i + 1, k - 1, s); int freq = 0, delCnt = 0, comp_len = 1; for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (freq == 1 || freq == 9 || freq == 99) comp_len++; freq++; } else { delCnt++; if (delCnt > k) break; } res = Math.min(res, comp_len + dfs(j + 1, k - delCnt, s)); } dp[i][k] = res; return res; } }

class Solution { private: int n; vector<vector<int>> dp; int dfs(int i, int k, const string& s) { if (n - i <= k) return 0; if (dp[i][k] != -1) return dp[i][k]; int res = 150; if (k > 0) res = dfs(i + 1, k - 1, s); int freq = 0, delCnt = 0, comp_len = 1; for (int j = i; j < n; j++) { if (s[i] == s[j]) { if (freq == 1 || freq == 9 || freq == 99) comp_len++; freq++; } else { delCnt++; if (delCnt > k) break; } res = min(res, comp_len + dfs(j + 1, k - delCnt, s)); } dp[i][k] = res; return res; } public: int getLengthOfOptimalCompression(string s, int k) { n = s.size(); dp = vector<vector<int>>(n + 1, vector<int>(k + 1, -1)); return dfs(0, k, s); } };

这里res = 150的取值是有讲究的：题面约束下字符串长度不超过 100，即使完全不压缩，RLE 长度也不会超过 150，因此150可以安全地作为"正无穷"哨兵参与min比较。

时间复杂度与空间复杂度

• 时间复杂度：$O(n^2 \cdot k)$
• 空间复杂度：$O(n \cdot k)$

其中 $n$ 是字符串 $s$ 的长度，$k$ 是允许删除的最大字符数。

相比解法一，空间从 $O(k \cdot n^2)$ 降到了 $O(n \cdot k)$，这是状态设计优化的直接收益。

解法三：动态规划（自底向上）

直觉

把优化版的自顶向下解法改写为自底向上形式：从右往左处理每个位置，为每个「位置 + 删除预算」组合计算最小编码长度。迭代填表方式避免了递归开销，也天然规避了递归深度问题。

算法步骤

1. 创建 2 维 DP 数组dp[n+1][k+1]，初始化为一个大值（如150），其中dp[n][*] = 0作为边界。
2. 从i = n-1递减到0，对每个rem_k从0到k。
3. 选项一：若rem_k > 0，令dp[i][rem_k] = dp[i+1][rem_k-1]（删除当前字符）。
4. 选项二：从i向前扫描，统计s[i]的频率与其它字符的删除数。维护压缩长度comp_len（初始为1，在阈值1、9、99处增加），并更新dp[i][rem_k] = min(dp[i][rem_k], comp_len + dp[j+1][rem_k - delCnt])。
5. 当delCnt > rem_k时停止扫描。
6. 返回dp[0][k]。

Python 实现

class Solution: def getLengthOfOptimalCompression(self, s: str, k: int) -> int: n = len(s) dp = [[150] * (k + 1) for _ in range(n)] dp.append([0] * (k + 1)) for i in range(n - 1, -1, -1): for rem_k in range(k + 1): if rem_k > 0: dp[i][rem_k] = dp[i + 1][rem_k - 1] freq = delCnt = 0 comp_len = 1 for j in range(i, n): if s[i] == s[j]: if freq in [1, 9, 99]: comp_len += 1 freq += 1 else: delCnt += 1 if delCnt > rem_k: break dp[i][rem_k] = min(dp[i][rem_k], comp_len + dp[j + 1][rem_k - delCnt]) return dp[0][k]

Java 与 C++ 实现

public class Solution { public int getLengthOfOptimalCompression(String s, int k) { int n = s.length(); int[][] dp = new int[n + 1][k + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { dp[i][j] = 150; } } for (int remK = 0; remK <= k; remK++) { dp[n][remK] = 0; } for (int i = n - 1; i >= 0; i--) { for (int remK = 0; remK <= k; remK++) { if (remK > 0) { dp[i][remK] = dp[i + 1][remK - 1]; } int freq = 0, delCnt = 0, compLen = 1; for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (freq == 1 || freq == 9 || freq == 99) { compLen++; } freq++; } else { delCnt++; if (delCnt > remK) break; } dp[i][remK] = Math.min(dp[i][remK], compLen + dp[j + 1][remK - delCnt]); } } } return dp[0][k]; } }

class Solution { public: int getLengthOfOptimalCompression(string s, int k) { int n = s.size(); vector<vector<int>> dp(n + 1, vector<int>(k + 1, 150)); for (int remK = 0; remK <= k; remK++) { dp[n][remK] = 0; } for (int i = n - 1; i >= 0; i--) { for (int remK = 0; remK <= k; remK++) { if (remK > 0) { dp[i][remK] = dp[i + 1][remK - 1]; } int freq = 0, delCnt = 0, compLen = 1; for (int j = i; j < n; j++) { if (s[i] == s[j]) { if (freq == 1 || freq == 9 || freq == 99) { compLen++; } freq++; } else { delCnt++; if (delCnt > remK) break; } dp[i][remK] = min(dp[i][remK], compLen + dp[j + 1][remK - delCnt]); } } } return dp[0][k]; } };

时间复杂度与空间复杂度

• 时间复杂度：$O(n^2 \cdot k)$
• 空间复杂度：$O(n \cdot k)$

其中 $n$ 是字符串 $s$ 的长度，$k$ 是允许删除的最大字符数。

自底向上版本在时间、空间复杂度上与优化版自顶向下完全一致，只是把递归换成了迭代填表，适合对递归栈深度敏感或希望常数更小的场景。

常见误区与排查指南

误区一：把游程编码长度算错

编码长度不随计数线性增长：单个字符为1（如"a"），计数 2~9 时为2（如"a5"），计数 10~99 时为3（如"a12"），计数 100 时为4（如"a100"）。长度只在1、9、99三个阈值处增加。漏掉这些阈值会导致长度计算错误——这也是三种解法中incr判断的共同核心。

误区二：没有考虑所有删除策略

只删除「破坏 run 的字符」这种贪心策略是错的。有时删除 run 内部的字符、或删除中间字符以合并两个同字符的 run，能得到更短的编码。因此 DP 必须对每个字符同时探索「保留」与「删除」两种选择。

误区三：状态表示不正确

朴素做法只追踪位置和剩余删除次数是不够的，还必须追踪前驱字符及其连续计数，才能正确计算对编码长度的贡献。优化版通过「向前扫描形成完整 run」的方式绕开了这一需求，从而把状态压缩到两维。

误区四：用无穷大导致的整数溢出

直接用INT_MAX或Integer.MAX_VALUE作为无穷大，再做加法会溢出。应改用较小的哨兵值（如150，它一定大于任何可能的答案），或者在执行算术运算前先判无穷。

误区五：循环终止的边界错误

向前扫描扩展 run 时，要正确处理j到达n的边界；「剩余字符可全部删除（n - i <= k）」的基础情况应返回0。在访问s[j]前不检查越界会引发运行时错误。

仓库中的实现与延伸阅读

本仓库围绕该题提供了可直接运行的多语言源码：

• articles/string-compression-ii.md：原文章，包含 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 共 10 种语言的三种解法完整代码；
• java/1531-string-compression-ii.java：Java 自顶向下朴素版（HashMap 字符串键缓存）；
• kotlin/1531-string-compression-ii.kt：Kotlin 自顶向下朴素版。

与之相关的游程编码主题文章还包括 articles/string-compression.md 与 articles/string-encode-and-decode.md，建议按「基础 RLE → 带删除预算的 RLE」的顺序串联学习，可以更清晰地体会「压缩长度阈值」这一考点在两类题目中的不同表现。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode