压缩字符串 II

难度: Hard

行程长度编码是一种常用的字符串压缩方法，它将连续的相同字符（重复 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 <= 100
0 <= k <= s.length
s 仅包含小写英文字母

Submission

运行时间: 308 ms

内存: 17.5 MB

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # 使用字典进行记忆化搜索，保存已经计算过的结果
        mem_dict = dict()
        
        def dfs(n, k):
            # 递归结束条件：当剩余字符数量小于等于删除数量时，返回0
            if n <= k:
                return 0
            
            # 构建当前递归调用的参数的键
            key = (n, k)
            
            # 如果当前参数已经计算过结果，则直接返回
            if key in mem_dict:
                return mem_dict[key]
            
            # 当可删除字符数量为0时，计算不删除任何字符的压缩长度
            if k == 0:
                res = 0
                j = 0
                for i in range(1, n):
                    if s[i] != s[i-1]:
                        d = i - j
                        if d == 1:
                            res += 1
                        elif d < 10:
                            res += 2
                        else:
                            res += 3
                        j = i
                d = n - j
                if d == 1:
                    res += 1
                elif d < 10:
                    res += 2
                elif d < 100:
                    res += 3
                else:
                    res += 4
                # 缓存计算结果
                mem_dict[key] = res
                return res
            
            # 初始化结果为递归调用，删除最后一个字符的结果
            res = dfs(n-1, k-1)
            c = 0
            # 从当前字符向前查找相同字符
            for i in range(n-1, -1, -1):
                if s[i] == s[n-1]:
                    c += 1
                    r = n - i - c
                    if r > k:
                        break
                    cur = dfs(i, k-r)
                    if c == 1:
                        cur += 1
                    elif c < 10:
                        cur += 2
                    elif c < 100:
                        cur += 3
                    else:
                        cur += 4
                    # 更新结果为最小值
                    if cur < res:
                        res = cur
            # 缓存计算结果
            mem_dict[key] = res
            return res
        
        # 调用递归函数，传入字符串长度和删除字符数量
        ret = dfs(len(s), k)
        return ret

Explain

此题解采用深度优先搜索（DFS）与记忆化的方法。首先，定义一个辅助函数dfs(n, k)，表示考虑前n个字符，允许删除k个字符时的最小压缩长度。使用记忆化存储，避免重复计算相同状态。在dfs函数中，首先检查递归结束条件，即当剩余字符数量小于等于可删除字符数量时，返回0。然后，检查当前状态是否已经计算过，如果是，则直接返回结果。接着，处理特殊情况，即当k为0时，计算不删除任何字符的压缩长度。最后，遍历剩余字符，对于每个字符，计算删除和不删除该字符的情况下的最小压缩长度，并更新结果。整体思路是通过递归分治的方式，枚举所有可能的删除操作，找到最优解。

时间复杂度: O(k * n^2)

空间复杂度: O(n * k)

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        # 使用字典进行记忆化搜索，保存已经计算过的结果
        mem_dict = dict()
        
        def dfs(n, k):
            # 递归结束条件：当剩余字符数量小于等于删除数量时，返回0
            if n <= k:
                return 0
            
            # 构建当前递归调用的参数的键
            key = (n, k)
            
            # 如果当前参数已经计算过结果，则直接返回
            if key in mem_dict:
                return mem_dict[key]
            
            # 当可删除字符数量为0时，计算不删除任何字符的压缩长度
            if k == 0:
                res = 0
                j = 0
                for i in range(1, n):
                    if s[i] != s[i-1]:
                        d = i - j
                        if d == 1:
                            res += 1
                        elif d < 10:
                            res += 2
                        else:
                            res += 3
                        j = i
                d = n - j
                if d == 1:
                    res += 1
                elif d < 10:
                    res += 2
                elif d < 100:
                    res += 3
                else:
                    res += 4
                # 缓存计算结果
                mem_dict[key] = res
                return res
            
            # 初始化结果为递归调用，删除最后一个字符的结果
            res = dfs(n-1, k-1)
            c = 0
            # 从当前字符向前查找相同字符
            for i in range(n-1, -1, -1):
                if s[i] == s[n-1]:
                    c += 1
                    r = n - i - c
                    if r > k:
                        break
                    cur = dfs(i, k-r)
                    if c == 1:
                        cur += 1
                    elif c < 10:
                        cur += 2
                    elif c < 100:
                        cur += 3
                    else:
                        cur += 4
                    # 更新结果为最小值
                    if cur < res:
                        res = cur
            # 缓存计算结果
            mem_dict[key] = res
            return res
        
        # 调用递归函数，传入字符串长度和删除字符数量
        ret = dfs(len(s), k)
        return ret

Explore

这一逻辑的依据是如果剩余的字符数不多于可以删除的字符数，那么理论上我们可以选择删除所有剩余字符，从而达到压缩字符串到0的长度。是的，这确实意味着在这种情况下，所有剩余的字符都可以被删除，因为删除后不会留下任何字符，也就没有压缩的必要，压缩长度因此为0。

当k为0时，确实直接计算了不删除任何字符的压缩长度。这种处理方式并未直接考虑所有字符都是相同的情况，而是通过遍历字符串并计算连续相同字符的压缩后长度来处理。计算方式是正确的，因为它按照连续字符的数量来决定使用1位、2位或更多位来表示重复次数，这符合压缩字符串的一般规则。

在处理k不为0的情况时，递归函数通过尝试两种策略来决定是否删除字符：一是尝试删除当前考虑的字符，并递归计算剩余部分的压缩长度；二是保留当前字符，并尝试找到与当前字符相同的一组字符，计算这些字符作为一个压缩单元的情况。具体策略是对于每个字符，尝试删除它并递归计算删除后的结果，同时遍历字符串，对于连续相同的字符，计算保留它们时的压缩长度，并递归计算剩余部分。然后取这些尝试中的最小值作为结果。这种策略允许算法在每一步都考虑保留或删除字符的最优决策，以达到全局最优的压缩长度。