最长k重复元素子串Python代码错误排查及修正需求

问题描述 #

定义 #

寻找最长k重复元素子串，其中k表示子串中元素的重复次数上限。示例：

• 字符串"ababcbb"，k=1时，最长子串为"babc"和"abcc"（分别以'b'、'c'为重复元素）；
• k=2时，最长子串为"babccb"（'b'重复3次、'c'重复2次）。
  程序要求从文件读取目标字符串。

现状 #

编写的Python代码运行结果不符合预期：

• 给定长字符串，k=3时，预期得到3个长度为22的子串及对应字符频率；
• 实际输出为长度32的子串及对应频率，需排查并修正代码错误。

常见错误分析 #

这类问题通常用滑动窗口算法实现，输出不符合预期的核心原因大概率出在窗口边界控制、频率统计或结果筛选逻辑上，具体可能的错误点：

1. 窗口收缩条件错误
   最常见的问题是只限制了窗口内出现次数最多的字符，而忽略了其他字符可能超过k的情况。比如错误地用max(freq.values()) > k作为收缩条件，导致部分字符超限时窗口仍未收缩，最终得到过长的子串。

2. 频率统计更新不及时
   滑动左边界时，未正确减少对应字符的频率计数，甚至未删除频率为0的字符，导致后续频率判断失真，窗口无法正确收缩。

3. 结果筛选逻辑缺失
   未记录所有长度等于最大值的子串，或在窗口仍不符合条件时就记录了子串，导致结果数量或长度不符合预期。

4. 文件读取冗余
   读取文件时未去除换行符、空格等冗余字符，导致处理的字符串长度比实际目标长，进而影响窗口计算。

修正后的代码实现 #

结合问题定义和预期结果，以下是修正后的Python代码：

from collections import defaultdict

def longest_k_repeat_substring(target_str, k):
    char_freq = defaultdict(int)
    left_ptr = 0
    max_sub_len = 0
    valid_substrings = []

    for right_ptr in range(len(target_str)):
        current_char = target_str[right_ptr]
        char_freq[current_char] += 1

        # 核心修正：收缩窗口直到所有字符的重复次数不超过k
        while any(count > k for count in char_freq.values()):
            left_char = target_str[left_ptr]
            char_freq[left_char] -= 1
            if char_freq[left_char] == 0:
                del char_freq[left_char]
            left_ptr += 1

        # 记录符合条件的子串
        current_sub_len = right_ptr - left_ptr + 1
        if current_sub_len > max_sub_len:
            max_sub_len = current_sub_len
            valid_substrings = [target_str[left_ptr:right_ptr+1]]
        elif current_sub_len == max_sub_len:
            valid_substrings.append(target_str[left_ptr:right_ptr+1])

    # 为每个子串生成字符频率统计
    result = []
    for sub in valid_substrings:
        sub_freq = defaultdict(int)
        for c in sub:
            sub_freq[c] += 1
        result.append((sub, dict(sub_freq)))
    
    return result

# 从文件读取目标字符串，去除冗余字符
with open("target_string.txt", "r") as f:
    input_str = f.read().strip()

# 测试参数
k_value = 3
final_result = longest_k_repeat_substring(input_str, k_value)

# 输出结果
for idx, (sub_str, freq) in enumerate(final_result, 1):
    print(f"子串 {idx}：长度={len(sub_str)}，字符频率={freq}")

关键修正说明 #

1. 窗口收缩逻辑：使用any(count > k for count in char_freq.values())作为收缩条件，确保窗口内所有字符的重复次数都不超过k，彻底避免超限制的子串。
2. 频率统计维护：滑动左边界时及时删除频率为0的字符，保证统计准确性。
3. 结果收集：完整记录所有长度等于最大值的子串，符合预期的多结果输出要求。
4. 文件读取处理：用strip()去除文件中可能存在的换行、空格等冗余字符，保证处理的字符串与目标一致。

内容的提问来源于stack exchange，提问作者Йохн Смит