求高效解法：在有限字母集长串中找各字符重复≤k次的最长子串

问题描述 #

给定一个由少量字母组成的长字符串，需要找到最长的子串（保持原有顺序），要求子串中每个字母的重复次数不超过k次。

示例 #

• 输入字符串：xyzxyxxxxxzzz，k=2
  满足条件的最长子串为xyzxy或yzxyx（每个字母出现次数均≤2）
• 输入字符串：abbbbcccddddabcd，k=1
  可行解为dabc或abcd（每个字母仅出现1次）

我的初步思路 #

1. 从左到右遍历字符串，用Python字典记录每个字母的出现次数
2. 若任一字母重复次数超过k，则在该字母出现的位置前截断字符串，将截断后的子串存入候选解数组
3. 继续遍历至字符串末尾，保存所有候选解
4. 对原字符串去掉首字符后的子串重复上述操作，递归执行直至字符串耗尽或剩余长度小于字母集的唯一字母数量

但我觉得这个方法太复杂，肯定有更高效简便的最优解法，暂时没想到。

最优解法：滑动窗口（双指针） #

这是处理这类子串约束问题的经典高效解法，时间复杂度为O(n)，远优于递归暴力法。核心思路是用左右两个指针维护一个"有效窗口"，确保窗口内所有字符的出现次数都不超过k，同时不断扩展窗口并记录最长的有效子串。

Python代码实现 #

def longest_substring_with_k_repeats(s, k):
    char_count = {}
    left = 0
    max_len = 0
    result = []
    
    for right in range(len(s)):
        # 更新当前字符的计数
        char = s[right]
        char_count[char] = char_count.get(char, 0) + 1
        
        # 当窗口存在违规字符时，移动左指针缩小窗口
        while max(char_count.values()) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1
        
        # 记录当前有效窗口的长度和子串
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            result = [s[left:right+1]]
        elif current_len == max_len:
            if s[left:right+1] not in result:
                result.append(s[left:right+1])
    
    return "或".join(result)

# 测试示例
print(longest_substring_with_k_repeats("xyzxyxxxxxzzz", 2))  # 输出xyzxy或yzxyx
print(longest_substring_with_k_repeats("abbbbcccddddabcd", 1))  # 输出abcd或dabc

方法细节 #

• char_count字典实时追踪窗口内每个字符的出现次数
• 右指针持续向右移动，将新字符加入窗口并更新计数
• 一旦窗口内有字符的出现次数超过k，就移动左指针，直到窗口重新满足条件
• 每次窗口有效时，检查并更新最长子串的记录，同时去重避免重复存储相同子串

这个方法无需递归或多次遍历原字符串，每个字符最多被左右指针各访问一次，处理长字符串时效率极高。

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