至少存在一个字符的子字符串的最小大小

Question

我有一个问题，想要k的最小长度，在长度为k的字符串的每个连续子串中，必须至少有一个公共字符。

例如如果 s="abcaca"

对于 k = 1 --> 子串是 [a]、[b]、[c] 等，我们根本找不到公共字符。 对于 k = 2 --> [ab], [bc], [ca] ...这又没有一个共同的字符

但是对于 k = 3，我们有 [abc]、[bca]、[cac] [aca]，a 和 c 都在所有子串中，所以答案是 k。

或者对于 s="abc" 我们有 k=2 与上面的描述相同。我的代码工作正确，但对于大长度的 s 来说并不是最佳的。谁能用动态滑动窗口或其他最佳方法解决这个问题？

n = input()

queue = list(n)

k = 1
s1 = 0
s2 = 1
last_intersection = None
sub_1 = set(queue[0:1])

while (s2 + k) < len(queue) + 1:
    sub_2 = set(queue[s2: s2 + k])
    if len(sub_2.intersection(sub_1)) > 0:
        sub_1 = sub_2.intersection(sub_1)
        s2 += 1
    else:
        s1 = 0
        s2 = 1
        k += 1
        sub_1 = set(queue[s1: s1 + k])

print(k)

Answer 1

逻辑如下：

s = "abcaca"
k = 1
n = len(s) # length of string s
while k < n:
    a = set(s[:k])
    for i in range(n - k):
        a &= set(s[i:i+k]) # intersection
        if not a: break  #if intersection is empty, no need to continue.
    if a: break #if after traversing the string, intersection is not empty, break
    k += 1
print(k)
3