假设我们有一个小写的字符串s和另一个值k。现在考虑一个操作，在该操作中，我们通过将重复的连续字符作为计数和字符对字符串执行行程编码。因此，如果字符串像“ aaabbc”，则将被编码为“ 3a2bc”。这里我们不将“ 1c”替换为“ c”，因为它仅连续出现一次。因此，我们可以先删除s中的任何k个连续字符，然后找到结果游程长度编码的最小可能长度。
因此，如果输入像s =“ xxxxxyyxxxxxzzxxx”，k = 2，则输出将为6，因为两个明显的选择是删除“ yy”或“ zz”。如果删除“ yy”，则将得到长度为7的“ 10x2z3x”。如果删除“ zz”，则将得到长度为6的“ 5x2y8x”，这是最小的。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数calc_cost()。这需要l
如果l等于0，则
返回0
如果l与1相同
返回1
除此以外，
str(l)+ 1的返回大小
定义一个功能prefix()。这将花费
如果c与最后一个相同，则
除此以外，
最后：= c
在pre中插入一个对（pre的最后一项的第0个元素，1 + pre的最后一项的第1元素）
将（pre的最后一项的第0个元素）+ calc_cost（pre的最后一项的第1元素，1）插入pre
pre：=最初带有对[0，0]的列表
最后：= null
对于s中的每个c
返回预
从主要方法执行以下操作：
pre：=前缀
suf：=前缀的反向（以相反的顺序）
ans：=无限
对于范围0到s-k + 1的i
成本：=成本+ calc_cost(midl)+ calc_cost(midr)
成本：=成本+ calc_cost（midl + midr）
j：= i + k
对（左，中）：= pre [i]
对（右，中）：= suf [j]
费用：=左+右
c1：= s [i-1]如果i> 0否则为null
c2：= s [j]如果j <s的大小，否则为null
如果c1与c2相同，则
除此以外，
ans：= ans和cost的最小值
返回ans
让我们看下面的实现以更好地理解-
def calc_cost(l):
if l == 0:
return 0
if l == 1:
return 1
else:
return len(str(l)) + 1
class Solution:
def solve(self, s, k):
def prefix(s):
pre = [[0, 0]]
last = None
for c in s:
if c == last:
pre.append([pre[-1][0], pre[-1][1] + 1])
else:
pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
last = c
return pre
pre = prefix(s)
suf = prefix(s[::-1])[::-1]
ans = float("inf")
for i in range(len(s) - k + 1):
j = i + k
left, midl = pre[i]
right, midr = suf[j]
cost = left + right
c1 = s[i - 1] if i > 0 else None
c2 = s[j] if j < len(s) else None
if c1 == c2:
cost += calc_cost(midl + midr)
else:
cost += calc_cost(midl) + calc_cost(midr)
ans = min(ans, cost)
return ans
ob = Solution()s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))s = "xxxxxyyxxxxxzzxxx"
输出结果
6