🥇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

下面是个人的代码:

  1. class Solution:
  2. def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
  3. di = {}
  4. for i in s:
  5. if i in di:
  6. di[i] += 1
  7. else:
  8. di[i] = 1
  9. c = sorted(di.items(), key=lambda item: item[1], reverse=True)
  10. m = []
  11. for i in c:
  12. if i[1] != 1:
  13. m.append(i[0])
  14. m.append(i[1])
  15. else:
  16. m.append(i[0])
  17. while k > 0:
  18. if str(m[-1]).isdigit():
  19. m[-1] -= 1
  20. if m[-1] == 0:
  21. m=m[0:len(m)-2]
  22. else:
  23. m=m[0:(len(m)-1)]
  24. k -= 1
  25. ans=''
  26. for i in m:
  27. if(i!=0):
  28. ans+=str(i)
  29. else:
  30. continue
  31. return len(ans)

image.png
正确的方法应该是要用DP