如何更快统计二进制字符串中非重叠全0子串的出现次数？

First off, let's address a critical issue with your current implementation: S.count('0'*N) actually counts overlapping substrings, which means it gives the wrong result for your requirement! For your example string "01000100" and N=2, count() would return 3 (since it counts the overlapping "00" in the middle three zeros), but the correct non-overlapping count is 2. On top of that, for ultra-long strings, count() can be inefficient because it has to scan for every occurrence of the target substring, and generating '0'*N for large N adds unnecessary memory overhead.

Here's a much faster, correct approach that runs in O(n) time with O(1) space—perfect for huge strings:

def myfunc(S, N):
    total = 0
    current_zero_streak = 0
    
    for char in S:
        if char == '0':
            current_zero_streak += 1
        else:
            # Calculate how many non-overlapping N-length zeros fit in the current streak
            total += current_zero_streak // N
            current_zero_streak = 0
    
    # Don't forget to count the final streak of zeros if the string ends with them
    total += current_zero_streak // N
    return total

Why this works better: #

• No overlapping counts: By tracking consecutive zero streaks, we calculate exactly how many non-overlapping N-length blocks fit in each streak (e.g., a streak of 3 zeros with N=2 gives 1 valid block, a streak of 5 gives 2).
• Minimal memory usage: We don't generate any large substrings (like '0'*N for huge N), which saves memory and avoids unnecessary string operations.
• Single pass: Each character in the string is processed exactly once—no backtracking or repeated scans, which is ideal for ultra-long inputs.

If you want an even more concise version (though the performance is nearly identical), you can use itertools.groupby to group consecutive characters:

from itertools import groupby

def myfunc(S, N):
    total = 0
    for char, group in groupby(S):
        if char == '0':
            streak_length = len(list(group))
            total += streak_length // N
    return total

This leverages groupby to split the string into runs of identical characters, then we just calculate the valid blocks for each zero run. Note that converting the group to a list to get its length is necessary here, but for most cases, it's still efficient enough for very long strings.

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