1531. 字符串压缩 II

Hard

题目描述

游程编码是一种字符串压缩方法，它通过将连续的相同字符（重复2次或更多次）替换为字符和表示字符计数的数字的连接来工作。例如，要压缩字符串 “aabccc”，我们将 “aa” 替换为 “a2”，将 “ccc” 替换为 “c3”。因此压缩后的字符串变为 “a2bc3”。

注意在这个问题中，我们不会在单个字符后添加 ‘1’。

给你一个字符串 s 和一个整数 k。你需要从 s 中删除最多 k 个字符，使得 s 的游程编码版本具有最小长度。

找到删除最多 k 个字符后 s 的游程编码版本的最小长度。

示例 1：

输入：s = "aaabcccd", k = 2
输出：4
解释：在不删除任何内容的情况下压缩 s 将给我们 "a3bc3d"，长度为 6。删除任何字符 'a' 或 'c' 最多会将压缩字符串的长度减少到 5，例如删除 2 个 'a'，然后我们将有 s = "abcccd"，压缩后是 abc3d。因此，最优的方法是删除 'b' 和 'd'，然后 s 的压缩版本将是 "a3c3"，长度为 4。

示例 2：

输入：s = "aabbaa", k = 2
输出：2
解释：如果我们删除两个 'b' 字符，结果压缩字符串将是 "a4"，长度为 2。

示例 3：

输入：s = "aaaaaaaaaaa", k = 0
输出：3
解释：由于 k 是 0，我们不能删除任何内容。压缩字符串是 "a11"，长度为 3。

约束：

1 <= s.length <= 100
0 <= k <= s.length
s 只包含小写英文字母

解题思路

这是一道复杂的动态规划题目。核心思想是通过状态转移找到在删除最多k个字符后能得到的最短压缩长度。

思路分析：

状态定义：dp[i][j] 表示处理前i个字符，删除j个字符后能得到的最短压缩长度。
转移策略：对于每个位置i，我们有两种选择：
- 删除当前字符：dp[i][j] = dp[i-1][j-1]（需要j>0）
- 保留当前字符：尝试将当前字符与前面的相同字符合并
关键优化：当保留当前字符时，我们需要考虑向前查找相同字符进行合并。设当前字符为s[i]，我们向前查找所有相同的字符，计算需要删除的不同字符数量。
压缩长度计算：对于连续的n个相同字符，压缩后的长度为：
- n = 1: 长度为1（只有字符本身）
- n ∈ [2,9]: 长度为2（字符+数字）
- n ∈ [10,99]: 长度为3（字符+两位数字）
- n ≥ 100: 长度为4（字符+三位数字）
状态转移方程：
```
dp[i][j] = min(
    dp[i-1][j-1],  // 删除当前字符
    dp[p-1][j-need] + getLen(same)  // 保留并合并
)
```
其中p是向前查找的起始位置，need是需要删除的字符数，same是合并后的相同字符数量。

这种方法的时间复杂度为O(n³k)，空间复杂度为O(nk)，对于题目给定的数据范围是可以接受的。

代码实现

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.length();
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, n + 1));
        dp[0][0] = 0;
        
        auto getLen = [](int cnt) {
            if (cnt == 0) return 0;
            if (cnt == 1) return 1;
            if (cnt < 10) return 2;
            if (cnt < 100) return 3;
            return 4;
        };
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 删除当前字符
                if (j > 0) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
                }
                
                // 保留当前字符，尝试与前面相同字符合并
                int same = 0, need = 0;
                for (int p = i; p >= 1; p--) {
                    if (s[p-1] == s[i-1]) {
                        same++;
                    } else {
                        need++;
                    }
                    
                    if (j >= need) {
                        dp[i][j] = min(dp[i][j], dp[p-1][j-need] + getLen(same));
                    }
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        def get_len(cnt):
            if cnt == 0:
                return 0
            elif cnt == 1:
                return 1
            elif cnt < 10:
                return 2
            elif cnt < 100:
                return 3
            else:
                return 4
        
        for i in range(1, n + 1):
            for j in range(k + 1):
                # 删除当前字符
                if j > 0:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1])
                
                # 保留当前字符，尝试与前面相同字符合并
                same = 0
                need = 0
                for p in range(i, 0, -1):
                    if s[p-1] == s[i-1]:
                        same += 1
                    else:
                        need += 1
                    
                    if j >= need:
                        dp[i][j] = min(dp[i][j], dp[p-1][j-need] + get_len(same))
        
        return dp[n][k]

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] = n + 1;
            }
        }
        dp[0, 0] = 0;
        
        int GetLen(int cnt) {
            if (cnt == 0) return 0;
            if (cnt == 1) return 1;
            if (cnt < 10) return 2;
            if (cnt < 100) return 3;
            return 4;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 删除当前字符
                if (j > 0) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i-1, j-1]);
                }
                
                // 保留当前字符，尝试与前面相同字符合并
                int same = 0, need = 0;
                for (int p = i; p >= 1; p--) {
                    if (s[p-1] == s[i-1]) {
                        same++;
                    } else {
                        need++;
                    }
                    
                    if (j >= need) {
                        dp[i, j] = Math.Min(dp[i, j], dp[p-1, j-need] + GetLen(same));
                    }
                }
            }
        }
        
        return dp[n, k];
    }
}

var getLengthOfOptimalCompression = function(s, k) {
    const n = s.length;
    const memo = new Map();
    
    function getLength(count) {
        if (count === 0) return 0;
        if (count === 1) return 1;
        if (count < 10) return 2;
        if (count < 100) return 3;
        return 4;
    }
    
    function dp(i, k, lastChar, lastCount) {
        if (k < 0) return Infinity;
        if (i === n) return 0;
        
        const key = `${i},${k},${lastChar},${lastCount}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = dp(i + 1, k - 1, lastChar, lastCount);
        
        if (s[i] === lastChar) {
            result = Math.min(result, 
                getLength(lastCount + 1) - getLength(lastCount) + dp(i + 1, k, lastChar, lastCount + 1)
            );
        } else {
            result = Math.min(result, 
                getLength(1) + dp(i + 1, k, s[i], 1)
            );
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, k, '', 0);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n³k)
空间复杂度	O(nk)

其中 n 是字符串长度，k 是最多删除的字符数。时间复杂度中的三个 n 分别来自：外层遍历位置 i，中层遍历删除数量 j，内层向前查找相同字符。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目