LeetCode 题解工作台
压缩字符串 II
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 "aabccc" ，将 "aa" 替换为 "a2" ， "ccc" 替换为` "c3" 。因此压缩后的字符串变为 "a2bc3" 。 注意，本问题…
2
题型
1
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution { public int getLengthOfOptimalCompression(String s, int k) {
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 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 <= 1000 <= k <= s.lengths仅包含小写英文字母
解题思路
方法一
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
// dp[i][k] := the length of the optimal compression of s[i..n) with at most
// k deletion
dp = new int[s.length()][k + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, K_MAX));
return compression(s, 0, k);
}
private static final int K_MAX = 101;
private int[][] dp;
private int compression(final String s, int i, int k) {
if (k < 0) {
return K_MAX;
}
if (i == s.length() || s.length() - i <= k) {
return 0;
}
if (dp[i][k] != K_MAX) {
return dp[i][k];
}
int maxFreq = 0;
int[] count = new int[128];
// Make letters in s[i..j] be the same.
// Keep the letter that has the maximum frequency in this range and remove
// the other letters.
for (int j = i; j < s.length(); ++j) {
maxFreq = Math.max(maxFreq, ++count[s.charAt(j)]);
dp[i][k] = Math.min(
dp[i][k], getLength(maxFreq) + compression(s, j + 1, k - (j - i + 1 - maxFreq)));
}
return dp[i][k];
}
// Returns the length to compress `maxFreq`.
private int getLength(int maxFreq) {
if (maxFreq == 1) {
return 1; // c
}
if (maxFreq < 10) {
return 2; // [1-9]c
}
if (maxFreq < 100) {
return 3; // [1-9][0-9]c
}
return 4; // [1-9][0-9][0-9]c
}
}
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They expect dynamic programming as soon as you notice that deleting inside a segment can improve a later merged run.
- question_mark
They are checking whether you understand that compression length changes only at count thresholds such as 1, 9, and 99.
- question_mark
They want a state definition that avoids storing the whole compressed string and instead measures only the minimum resulting length.
常见陷阱
外企场景- error
Using a greedy rule like deleting the least frequent character first misses cases where removing separators creates a much shorter merged run.
- error
Forgetting that a single character contributes length 1, not 2, leads to wrong transitions for small runs.
- error
Not charging deletions for non-matching characters inside the current window breaks the run-forming DP transition.
进阶变体
外企场景- arrow_right_alt
Return the compressed string itself after at most k deletions instead of only its minimum length.
- arrow_right_alt
Change the encoding rule so single characters also store a count, which alters every threshold and DP cost.
- arrow_right_alt
Limit deletions to exactly k characters, which changes base cases and may force harmful removals near the end.