class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
}
};
1531. 压缩字符串 II
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 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 仅包含小写英文字母原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-06 23:48:15
// dp[p][cnt] 从 p到N-1 选择了cnt个字符 的最小压缩长度
var dp [101][101]int
func getLengthOfOptimalCompression(s string, k int) int {
n := len(s) // 总字符数
m := n - k // 最大允许选择字符数
for i := 0; i <= n; i++ {
for j := 0; j <= m; j++ {
dp[i][j] = n // 初始化为最大值
}
}
dp[n][0] = 0
// debug(n, m)
for p := n - 1; p >= 0; p-- {
for cnt := 0; cnt <= m && cnt < n-p; cnt++ {
//case1: 不选， 即从 p+1 中选出cnt个字符的个数
dp[p][cnt] = min(dp[p][cnt], dp[p+1][cnt])
}
// case2： 选择 s[p]，有多种合法转移场景:
// 第一部分: p ~ j: 之间选择 和 s[p] 相同的 same 个 字符
// 第二部分: j+1 ~ n-1: 之间选择 cnt 个字符， cnt 范围 0 ~ n-j-1
// same + cnt 不超过最长选择长度 m
for j, same := p, 0; j < n; j++ {
if s[p] == s[j] {
same++
}
for cnt := 0; cnt <= n-j-1 && cnt <= m-same; cnt++ {
dp[p][same+cnt] = min(dp[p][same+cnt], dp[j+1][cnt]+calc(same))
}
}
// debug(n, m)
}
return dp[0][n-k] // 取从0 ~ N-1 之间选择n-k个字符，压缩距离最小的值
}
func calc(same int) int {
switch {
case same <= 1:
return 1
case same <= 9:
return 2
case same <= 99:
return 3
default:
return 4
}
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func debug(n, m int) {
for i := 0; i <= n; i++ {
for j := 0; j <= m; j++ {
fmt.Print(dp[i][j], "\t")
}
fmt.Println()
}
fmt.Println()
}
java 解法, 执行用时: 32 ms, 内存消耗: 40.1 MB, 提交时间: 2023-09-06 23:47:36
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
int n = s.length();
int[][] f = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(f[i], Integer.MAX_VALUE >> 1);
}
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k && j <= i; ++j) {
if (j > 0) {
f[i][j] = f[i - 1][j - 1];
}
int same = 0, diff = 0;
for (int i0 = i; i0 >= 1 && diff <= j; --i0) {
if (s.charAt(i0 - 1) == s.charAt(i - 1)) {
++same;
f[i][j] = Math.min(f[i][j], f[i0 - 1][j - diff] + calc(same));
} else {
++diff;
}
}
}
}
return f[n][k];
}
public int calc(int x) {
if (x == 1) {
return 1;
}
if (x < 10) {
return 2;
}
if (x < 100) {
return 3;
}
return 4;
}
}
python3 解法, 执行用时: 1260 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-06 23:47:19
'''
动态规划
f[i][j] 表示对于原串 s 的前 i 个字符，通过删除其中的 j 个字符，
剩余的 i−j 个字符可以得到的最小的压缩串的长度。
'''
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))
n = len(s)
f = [[10**9] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(min(k, i) + 1):
if j > 0:
f[i][j] = f[i - 1][j - 1]
same = diff = 0
for i0 in range(i, 0, -1):
if s[i0 - 1] == s[i - 1]:
same += 1
f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))
else:
diff += 1
if diff > j:
break
return f[n][k]