1531. String Compression II

题目信息

题号:

1531

难度:

Hard

主题:

字符串、动态规划、游程编码

原题:

LeetCode 1531

重点:

最多删除 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
解释:删除全部字符后结果为空串。