🥇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