找出最多有 K 个重复字符的最长子串的长度

Question

问题：给定整数 n, k (1 <= n <= 100.000), (1 <= k <= n)。找出最多有 K 个重复字符的最长子串的长度，并从原始字符串中找出子串中第一个元素的位置。例子
输入：6、2 'abbbaa' output: 4 3 //这里，4是最大长度，3是子串'bbaa'的第一个元素在原字符串中的位置。这样，这里每个字符重复k次，就可以了

输入：3、1 'abb' output: 2, 1 //是的，需要的子串是 'ab' 我希望声明是清楚的，至少我试过了，`因为英语不是我的母语。

不知道如何着手设计这个问题的算法。我应该使用二进制搜索答案技术，因为从任务的陈述看来。

首先要做的事情是：我至少尝试发展我的想法来解决这个问题，所以它是：

找到中间，我们将字符串从0到mid+1和mid到n分成两片。（我在 Python 中编码，所以我认为这里使用切片是很自然的）
寻找唯一字符的数量（我使用了 len(set(slice))）并比较：如果第一个（左）切片的数量更大，那么我们改变 right = mid，否则左
所有这些指令都放在 'while right > left + 1' 循环中。

到目前为止一切顺利，但可能我错过了什么，或者这个想法不是一个有效的想法来获取子字符串的第一个元素的位置，查看它在给定字符串中的位置。

代码(Python3)：找到第一个元素的位置，使用binsearch

n, k = map(int, input().split())
s = input()
left = 0
right = n - 1

while (right > left + 1):
    mid = (left + right) // 2
    char1 = len(set(s[0:mid+1]))
    char2 = len(set(s[mid:n]))
    if char1 >= char2:
        right = mid
    else:
        left = mid
print(left + 1)

不使用 bin.search 查找最长子串长度的代码（我认为这会更容易，而且效果很好，尽管方法很幼稚）

n, k = map(int, input().split())
s = input()
letters = [0] * 26
max_len = 0
for i in range(len(s)):
    letters[ord(s[i]) - ord('a')] = letters[ord(s[i]) - ord('a')] + 1
for i in range(0, 26):
    if letters[i] >= k:
        max_len = max_len + k
    else:
        max_len = max_len + letters[i]
print(max_len)

Answer 1

你的方法是贪婪的，不会得到正确的结果。考虑输入 4 4 ccab - 您的二进制搜索代码将 return 2，但它应该 return 1（整个字符串是好的）。要解决这个问题，您可以使用称为两个指针的方法。我们定义两个指针 a 和 b 作为我们当前正在考虑的子串的开始和结束。我们还需要记住当前子串中每个字母出现的次数。首先，将 a 和 b 设置为 0。然后尝试通过将其末尾移动 1 (b=b+1) 来扩展当前子串，同时将字母 s[b] 的出现次数增加 1。如果这个数字超出 K 这意味着我们当前的字符串不再有效。为了使其再次有效，我们需要将其开始移动到子字符串 (a, b) 的所有字母出现少于或恰好 K 次的点。为此，我们只需将 a 递增 1 并递减 oc[s[a]] 直到 oc[s[b]] <= k。时间复杂度是线性的，因为我们恰好将 b 递增 n 次，而 a 最多递增 n 次。在每一步中，我们还检查是否 b-a+1>max_len 如果是，则将 max_len 设置为 b-a+1 并将开头设置为 a.

n, k = map(int, input().split())
s = input()
a = 0
oc = [0]*26
max_len = 0
first = -1

for b in range(0, n):
    oc[ord(s[b])-ord('a')]+=1
    while(oc[ord(s[b])-ord('a')]>k):
        oc[ord(s[a])-ord('a')]-=1
        a+=1
    if b-a+1>max_len:
        max_len=b-a+1
        first=a+1

print(first)
print(max_len)

oc 是我们存储子字符串中出现的字母的数组。

找出最多有 K 个重复字符的最长子串的长度

Find the length of longest substring with at most K repeating characters

python

string

algorithm

binary-search