我已经阅读了类似的问题,但找不到任何已经发布的问题与我的类似。
问题: 在一个由少量字母组成的长字符串中(该字符串的字母表相对较小),找到每个字母最多包含 k 个重复的最长可能子串(保持顺序不变)。
示例: 输入字符串xyzxyxxxxxzzz; k=2。 这里我们有一个来自字母表 {x, y, z} 的字符串。没有字母重复超过 2 次的最长可能子串是 xyzxy 或 yzxyx。
又一个例子:abbbbcccddddabcd; k=1。 解决方案可以是 dabc、abcd 中的任何一个。
我不太清楚如何将解决方案形式化为代码。我正在考虑的方法是:
不知何故,我认为这太复杂了,必须有一个更简单的解决方案,这是显而易见的,但由于某种原因我看不到它。
您的方法距离有效的解决方案并不遥远。这最适合“滑动窗口”算法,其中窗口可以在右侧增大并从左侧缩小。所以你的第二步需要改变 代替:
如果任何字母重复超过 k 次,则剪掉令人反感的字母之前的字符串,将其保留在可能的解决方案数组中
做:
如果任何字母重复超过 k 次,则将字符串
从左侧剪切到该违规字母第一次出现的位置。
不需要递归。在当前窗口右侧添加字符的每一步,检查它是否比迄今为止最好的字符长。
实施:
from collections import defaultdict
def solve(s, k):
freq = defaultdict(int)
left = 0
bestLeft = 0
bestRight = -1
for right, ch in enumerate(s):
if freq[ch] < k:
freq[ch] += 1
else:
while s[left] != ch:
freq[s[left]] -= 1
left += 1
left += 1
if right - left >= bestRight - bestLeft:
bestLeft, bestRight = left, right
return s[bestLeft: bestRight+1]
s = "xyzxyxxxxxzzz"
k = 2
print(solve(s, k)) # xyzxy
s = "abbbbcccddddabcd"
k = 1
print(solve(s, k)) # dabc