🥇5462. 压缩字符串 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 仅包含小写英文字母

  题解

  个人思路

  这道题花了一个小时，当时考虑的是先生成类似于a3b2c这样的字符串（数组），其中字母是按照个数排序的。然后根据给的k，从后往前删除。但这样忽略了另一种情况，比如a10c9，输入的k=1，按照我的方法结果是a10c8，而正确结果是a9c8！

下面是个人的代码：

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        di = {}
        for i in s:
            if i in di:
                di[i] += 1
            else:
                di[i] = 1
        c = sorted(di.items(), key=lambda item: item[1], reverse=True)
        m = []
        for i in c:
            if i[1] != 1:
                m.append(i[0])
                m.append(i[1])
            else:
                m.append(i[0])
        while k > 0:
            if str(m[-1]).isdigit():
                m[-1] -= 1
                if m[-1] == 0:
                    m=m[0:len(m)-2]
            else:
                m=m[0:(len(m)-1)]
            k -= 1
        ans=''
        for i in m:
            if(i!=0):
                ans+=str(i)
            else:
                continue
        return len(ans)

正确的方法应该是要用DP