在由少量有限数量的唯一字母组成的长字符串中,找到包含重复不超过 k 次的所有唯一字母的最长子字符串

问题描述 投票:0回答:1

我已经阅读了类似的问题,但找不到任何已经发布的问题与我的类似。

问题: 在一个由少量字母组成的长字符串中(该字符串的字母表相对较小),找到每个字母最多包含 k 个重复的最长可能子串(保持顺序不变)。

示例: 输入字符串xyzxyxxxxxzzz; k=2。 这里我们有一个来自字母表 {x, y, z} 的字符串。没有字母重复超过 2 次的最长可能子串是 xyzxy 或 yzxyx。

又一个例子:abbbbcccddddabcd; k=1。 解决方案可以是 dabc、abcd 中的任何一个。

我不太清楚如何将解决方案形式化为代码。我正在考虑的方法是:

  • 从左到右读取字符串,并且将字母表中每个唯一字母的每次出现次数保存在 Python 字典中
  • 如果任何字母重复超过 k 次,则剪掉令人反感的字母之前的字符串,将其保留在可能的解决方案数组中
  • 继续阅读字符串到最后并保留任何可能的解决方案
  • 对原始字符串减去第一个字母的子字符串执行相同的操作,并递归调用,直到字符串耗尽或者剩下的字符串少于字母表中的唯一字母

不知何故,我认为这太复杂了,必须有一个更简单的解决方案,这是显而易见的,但由于某种原因我看不到它。

python algorithm
1个回答
0
投票

您的方法距离有效的解决方案并不遥远。这最适合“滑动窗口”算法,其中窗口可以在右侧增大并从左侧缩小。所以你的第二步需要改变 代替:

如果任何字母重复超过 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

© www.soinside.com 2019 - 2024. All rights reserved.