字符串压缩 IILeetCode 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这种形式长度为210~99次时为a12长度为3100次时为a100长度为4。连续出现次数编码示例编码长度相比上一档新增1a1—2 ~ 9a2~a92第 1 个字符之后新增 1 位数字10 ~ 99a10~a993到达 10 时新增 1 位数字100a1004到达 100 时新增 1 位数字可以看到编码长度并不是随计数线性增长的它只在计数越过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保留或删除当前字符。算法步骤定义count(i, k, prev, prev_cnt)i为当前下标k为剩余删除次数prev为前一个字符prev_cnt为该字符已连续出现的次数。边界情况若k 0返回无穷大非法若i n返回0。若s[i] prev延续当前 run仅当prev_cnt为1、9、99时结果加1编码长度增长的阈值点。若s[i] ! prev取两种选择的最小值删除s[i]消耗一次删除机会或保留s[i]开启新 run长度贡献1。使用 4 维缓存做记忆化。返回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) # dont 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 { MapString, 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 版本 的结构完全相同同样以HashMapString, Int缓存、用Z作为哨兵前驱字符class Solution { fun getLengthOfOptimalCompression(s: String, k: Int): Int { val cache HashMapString, 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; vectorvectorvectorvectorint 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); // dont 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 vectorvectorvectorvectorint( n 1, vectorvectorvectorint(k 1, vectorvectorint(27, vectorint(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。这样状态空间被压缩到只剩「位置 剩余删除次数」两个维度。算法步骤定义dfs(i, k)i为当前下标k为剩余删除预算。边界情况若n - i k说明剩余字符可以全部删掉返回0。选项一若k 0删除s[i]得到dfs(i 1, k - 1)。选项二以s[i]开启一个 run。向前扫描统计匹配字符数、删除不匹配字符数。实时维护压缩长度comp_len在计数为1、9、99时增加。对每个扫描终点计算comp_len dfs(j 1, k - delCnt)。取所有选项的最小值。用 2 维缓存dp[n][k1]记忆化。返回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; vectorvectorint 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 vectorvectorint(n 1, vectorint(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)$这是状态设计优化的直接收益。解法三动态规划自底向上直觉把优化版的自顶向下解法改写为自底向上形式从右往左处理每个位置为每个「位置 删除预算」组合计算最小编码长度。迭代填表方式避免了递归开销也天然规避了递归深度问题。算法步骤创建 2 维 DP 数组dp[n1][k1]初始化为一个大值如150其中dp[n][*] 0作为边界。从i n-1递减到0对每个rem_k从0到k。选项一若rem_k 0令dp[i][rem_k] dp[i1][rem_k-1]删除当前字符。选项二从i向前扫描统计s[i]的频率与其它字符的删除数。维护压缩长度comp_len初始为1在阈值1、9、99处增加并更新dp[i][rem_k] min(dp[i][rem_k], comp_len dp[j1][rem_k - delCnt])。当delCnt rem_k时停止扫描。返回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(); vectorvectorint dp(n 1, vectorint(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.javaJava 自顶向下朴素版HashMap 字符串键缓存kotlin/1531-string-compression-ii.ktKotlin 自顶向下朴素版。与之相关的游程编码主题文章还包括 articles/string-compression.md 与 articles/string-encode-and-decode.md建议按「基础 RLE → 带删除预算的 RLE」的顺序串联学习可以更清晰地体会「压缩长度阈值」这一考点在两类题目中的不同表现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
