求满足所有长度为k的连续子串含公共字符的最小k值的最优解法

需要找到最小的k值，使得目标字符串中所有长度为k的连续子串都至少包含一个公共字符。举例：

• 当s="abcaca"时，k=1、2时所有子串无公共字符，k=3时所有子串均包含a或c，故答案为3；
• 当s="abc"时答案为2。

原代码可正确运行，但处理长字符串时效率不足，询问能否用滑动窗口或其他优化方法实现。

原代码 #

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)

原代码采用逐次尝试k值的思路，从k=1开始逐个检查所有长度为k的子串是否存在公共交集。每次检查子串都需要生成集合并计算交集，时间复杂度为O(n²)，当字符串长度达到1e4甚至1e5时，运算量会急剧增加，导致效率低下。

核心思路 #

问题可转化为：找到最小的k，使得存在某个字符c，所有长度为k的连续子串都包含c。反过来，对于每个字符c，只需计算字符串中最长的连续不包含c的子串长度max_len。要保证所有长度k的子串都包含c，k必须大于这个max_len（因为若k > max_len，任何长度k的子串都不可能完全避开c）。最终答案就是所有字符对应的max_len + 1中的最小值。

该思路时间复杂度为O(n*m)，其中m是字符串中不同字符的数量（对于小写字母，m=26，可视为线性时间），完全适配超长字符串场景。

示例验证 #

• 对于s="abcaca"：
  • 字符a：最长无a子串为"bc"，长度2 → 需k≥3
  • 字符b：最长无b子串为"caca"，长度4 → 需k≥5
  • 字符c：最长无c子串为"ab"，长度2 → 需k≥3
    取最小值3，符合预期。
• 对于s="abc"：
  • 字符a：最长无a子串为"bc"，长度2 → 需k≥3
  • 字符b：最长无b子串为"a"和"c"，最长1 → 需k≥2
  • 字符c：最长无c子串为"ab"，长度2 → 需k≥3
    取最小值2，符合预期。

实现代码 #

基础版本 #

def min_k(s):
    if not s:
        return 0
    unique_chars = set(s)
    min_required = float('inf')
    
    for c in unique_chars:
        current_max = 0
        current_len = 0
        for char in s:
            if char != c:
                current_len += 1
                current_max = max(current_max, current_len)
            else:
                current_len = 0
        required = current_max + 1
        if required < min_required:
            min_required = required
    return min_required

# 测试用例
print(min_k("abcaca"))  # 输出3
print(min_k("abc"))     # 输出2

滑动窗口版本 #

def min_k_sliding_window(s):
    if not s:
        return 0
    unique_chars = set(s)
    min_required = float('inf')
    
    for c in unique_chars:
        left = 0
        max_len = 0
        for right in range(len(s)):
            if s[right] != c:
                max_len = max(max_len, right - left + 1)
            else:
                left = right + 1
        required = max_len + 1
        if required < min_required:
            min_required = required
    return min_required

# 测试用例
print(min_k_sliding_window("abcaca"))  # 输出3
print(min_k_sliding_window("abc"))     # 输出2

内容的提问来源于stack exchange，提问作者Amir Hossein