LeetCode 1531. 压缩字符串 II
题目描述
原题：1531. 压缩字符串 II。
给定小写英文字母字符串 s 和非负整数 k，允许先删除至多k个字符，再按连续相同字符压缩。连续1个只写字符，多个写字符及次数。返回最小压缩长度。
示例 1：
输入：s = "aaabbbaaa", k = 3
输出：2
解释：删除三个 b 后得到 "aaaaaa"，压缩为 "a6"，长度为 2。
提示：
- s 只含小写英文字母；k 为非负整数且不超过 s 的长度。最多删除 k 个字符，出现一次的连续字符不附加数字 1。
题意分析
先从字符串中删除至多
k个字符，再把剩余字符串的每段连续相同字符压缩，求压缩后最短的长度。删除后保留字符的相对顺序，原来被其他字符隔开的同字符段可能因此合并。长度为一的段只写字符，不写次数一；更长的段写一个字符再加次数的十进制表示。因此代价由连续段及段长决定，不等于剩余字符数，也不能只根据原字符串已经分好的段独立选择删除。
解法：后缀删除预算 DP 与连续段合并
核心思路
[!blue]
定义
dp[i][d]为后缀s[i:n]在最多还能删除d个字符时，能够得到的最短编码长度。空后缀无论还剩多少预算，代价都是零，所以dp[n][d] = 0。状态依赖更靠右的后缀，按i从大到小计算即可。第一种选择是删除
s[i]。预算至少为一时，代价为dp[i + 1][d - 1]；没有预算时这条分支不可用。第二种选择是保留
s[i]，让它成为剩余字符串第一段的字符。向右枚举扫描终点j，same统计这一范围内与s[i]相同的字符数，removed统计其他字符数。把其他字符都删除，就能将这些相同字符连成一段，消耗removed次预算，后面的剩余问题为dp[j + 1][d - removed]。这一段的编码长度由
same决定：一份时长度为一，否则是一个字符加次数的十进制位数。把它与后缀代价相加，更新当前最小值。扫描越往右，需要删除的其他字符只会增多，一旦removed > d，再延伸也无法满足预算，可以停止当前扫描。保留分支不单独枚举删除段内的同字符，并不会漏掉最优结果：若某段确实要删掉若干个该字符，可以把这些等价的删除移到该段开头，留下的段长、字符顺序和删除总数都不变，交给前面的“删除当前字符”分支即可。因此一定存在一个最优方案，在首个保留字符到这段结束之间保留全部同字符、删除全部不同字符。
枚举段终点也处理了删除后的跨段合并。如果剩余后缀还能与当前段连成更长的同字符段，继续向右枚举就会考虑把它们合并的选择，不必预先锁定原字符串的分段。删除与保留两类选择共同覆盖最优方案，答案为
dp[0][k]，不要求把预算全部用完。
解题步骤
- 创建后缀和删除预算的状态表，空后缀一行全部设为零。
- 倒序枚举起点
i，对每个预算d先考虑删除当前字符；无预算时将该候选设为不可行的大值。- 保留当前字符并向右枚举终点，累计
same和removed；预算超额则停止扫描。- 用当前段编码长度加剩余后缀最优代价更新最小值，写入
dp[i][d]。- 返回
dp[0][k]。
代码实现
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
int n = s.length();
int[][] dp = new int[n + 1][k + 1];
for (int i = n - 1; i >= 0; i--) {
for (int d = 0; d <= k; d++) {
int best = d > 0 ? dp[i + 1][d - 1] : n + 1;
int same = 0;
int removed = 0;
for (int j = i; j < n; j++) {
if (s.charAt(j) == s.charAt(i)) {
same++;
} else {
removed++;
}
if (removed > d) {
break;
}
int length = same == 1 ? 1 : 1 + Integer.toString(same).length();
best = Math.min(best, length + dp[j + 1][d - removed]);
}
dp[i][d] = best;
}
}
return dp[0][k];
}
}
func getLengthOfOptimalCompression(s string, k int) int {
n := len(s)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
}
for i := n - 1; i >= 0; i-- {
for d := 0; d <= k; d++ {
best := n + 1
if d > 0 {
best = dp[i+1][d-1]
}
same, removed := 0, 0
for j := i; j < n; j++ {
if s[j] == s[i] {
same++
} else {
removed++
}
if removed > d {
break
}
length := 1
if same > 1 {
for x := same; x > 0; x /= 10 {
length++
}
}
best = min(best, length+dp[j+1][d-removed])
}
dp[i][d] = best
}
}
return dp[0][k]
}
复杂度分析
- 时间复杂度：$O(n^2(k+1))$。有
n(k + 1)个状态，每个状态最多向右扫描n个位置；原题n <= 100，次数最多三位，计算段编码长度的开销为常量。- 空间复杂度：$O(n(k+1))$，保存全部后缀与预算状态。写成
k + 1包括零删除预算也需要计算的情况。
关键点总结
[!green]
- 预算表示最多还能删除多少字符，空后缀不要求继续花完预算。
- 保留首字符后枚举它所在的首段，扫描中的不同字符被删除，同字符通过删除连接起来。
- 段代价取决于次数的十进制位数，而不是简单正比于保留数量。
- 原来的分段可能变化，必须允许向右跨过并删除不同字符后继续合并。
易错点总结
[!yellow]
- 把每个原始连续段独立优化，会漏掉删除中间字符后合并前后同字符段的收益。
- 长度一也附加次数，会错误增加单字符段的编码长度。
- 把重复次数的编码始终当成一位，跨过十进制位数边界时会算错代价。
- 使用
d - same作为剩余预算，混淆了保留数量与删除数量；应减去removed。- 将最多删除解释成必须删除，会错误限制未花完预算的可行最优状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 443. 压缩字符串 | 中等 | 删除预算为 0 时退化为连续段压缩；允许删除后可能合并原本分离的相同字符段。 |