如何正确统计二进制字符串中不同长度子串的出现频率

这个问题的核心矛盾是Python原生str.count()方法默认采用非重叠匹配逻辑：命中一个子串后，指针会直接跳过整个子串长度向后检索，无法识别重叠的匹配项，比如'000'.count('00')只会返回1，漏掉索引1-2位置的重叠00。

最优实现：单遍滑动窗口 #

时间复杂度O(n)，逻辑直白不容易出错，是工业场景最常用的写法：

• 固定窗口长度为传入的统计长度length
• 从字符串起始位置开始，每次窗口向后移动1位（不是移动length位），截取当前窗口的子串
• 用哈希表累计每个子串的出现次数

参考实现：

from collections import defaultdict

def count_substr_freq(s: str, length: int) -> dict:
    str_len = len(s)
    if length <= 0 or str_len < length:
        return {}
    freq = defaultdict(int)
    # 遍历所有合法的窗口起始位置，步长1保证覆盖所有重叠子串
    for start in range(str_len - length + 1):
        current_sub = s[start:start+length]
        freq[current_sub] += 1
    return dict(freq)

用题目给出的样例验证：调用count_substr_freq('0100011', 2)，返回结果为{'01': 2, '10': 1, '00': 2, '11': 1}，完全符合预期；对'000'统计长度2的子串时，会正确返回{'00':2}，解决了原生count的漏算问题。

更简洁的标准库实现 #

如果不想手动计算索引，可以借助zip和Counter用更短的代码实现相同逻辑，性能和滑动窗口基本一致：

from collections import Counter

def count_substr_freq_zip(s: str, length: int) -> dict:
    str_len = len(s)
    if length <= 0 or str_len < length:
        return {}
    # 构造k个错位的字符串序列，zip逐位配对正好得到所有连续k长子串
    window_iter = zip(*(s[i:] for i in range(length)))
    return dict(Counter(''.join(chars) for chars in window_iter))

避坑说明 #

不要尝试通过循环调用count()+调整起始位置的方式实现，这种写法会重复遍历字符串，时间复杂度会升高到O(n*k)，远不如单遍滑动窗口高效，也更容易写错边界条件。

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