1531. String Compression II¶
题目信息¶
- 题号:
1531
- 难度:
Hard
- 主题:
字符串、动态规划、游程编码
- 原题:
- 重点:
最多删除
k个字符后,对剩余字符串做连续字符计数压缩;计数为一时不写数字,求最短压缩长度
题目重述¶
给定小写字符串 s 和整数 k。可以从 s 中删除至多 k 个字符,剩余字符保持原相对顺序。
随后对字符串做游程编码:每段连续相同字符写成字符本身;若段长大于一,再紧跟十进制次数。请返回所有删除方案中压缩结果的最小长度。
1 <= s.length <= 100,0 <= k <= s.length。
自建示例¶
删除分隔字符可以合并相同字符段:
输入:s = "aaabcc", k = 2
输出:3
解释:删除 b 和一个 c 后得到 "aaac",压缩为 "a3c",长度为 3。
允许删除全部字符时压缩长度为零:
输入:s = "abc", k = 3
输出:0
解释:删除全部字符后结果为空串。