在Python中删除最多k个字符后查找运行长度编码的最小长度的程序
假设我们有一个字符串s和另一个值k。我们最多可以从s中删除k个字符，使得s的游程编码版本的长度最小。众所周知，行程编码是一种字符串压缩方法，它用字符和标记字符计数的数字的串联替换连续的相同字符（2次或更多次）。例如，如果我们有一个字符串“xxyzzz”，那么我们用“x2”替换“xx”，用“z3”替换“zzz”。所以压缩的字符串现在是“x2yz3”。所以在这个问题中，我们必须在删除最多k个值后找到s的游程编码版本的最小长度。
所以，如果输入像s="xxxyzzzw",k=2，那么输出将是4，因为字符串s没有删除任何东西，游程编码是"x3yz3w"长度6。如果我们删除两个字符并使s像“xzzzw”或“xyzzz”那么压缩版本将是“xz3w”，“xyz3”的长度都是4。
示例
让我们看下面的实现来更好地理解
def solve(s, k):
if k >= len(s):
return 0
if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
if k == 0:
return 4
if k <= 90:
return 3
if k <= 98:
return 2
return 1
def f(p, k, c, l2):
if k < 0:
return 10000
if p < 0:
return 0
if c == s[p]:
return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
else:
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
return f(len(s)-1, k, None, 0)
s = "xxxyzzzw"
k = 2
print(solve(s, k))输入
"xxxyzzzw", 2输出结果
4