如何统计二进制字符串中满足指定条件的不同子串数量

首先明确符合要求的子串的核心特征：所有0在前、所有1在后，且0和1的数量相等，因此这类子串的结构必然是 k个0 + k个1，k为正整数。不同的子串仅由k值决定，k相同则子串内容完全一致。

步骤 #

• 第一步：将原二进制字符串转换为连续相同字符的块序列，每个块记录字符类型和连续出现的长度。例如输入001101会被转换为 [('0', 2), ('1', 2), ('0', 1), ('1', 1)]。
• 第二步：遍历所有相邻的块对：
  • 仅当前一个块是0块、后一个块是1块时，才能生成符合要求的子串
  • 这对块能支撑的最大k值为 min(0块长度, 1块长度)，所有1≤k≤该最大值的k均为有效取值
• 第三步：用集合存储所有有效k值（自动去重），最终集合的大小就是不同子串的数量。

示例验证 #

以输入001101为例：

第一对相邻块为(0,2)和(1,2)，min值为2，得到有效k值1、2，集合为{1,2}
第二对相邻块为(1,2)和(0,1)，前块是1后块是0，跳过
第三对相邻块为(0,1)和(1,1)，min值为1，得到有效k值1，集合无变化
最终集合大小为2，和示例结果一致。

参考代码（Python） #

def count_unique_valid_substrings(s: str) -> int:
    if not s:
        return 0
    # 生成连续字符块序列
    blocks = []
    current_char = s[0]
    count = 1
    for c in s[1:]:
        if c == current_char:
            count += 1
        else:
            blocks.append((current_char, count))
            current_char = c
            count = 1
    blocks.append((current_char, count))
    
    valid_k = set()
    # 遍历相邻块对
    for i in range(len(blocks) - 1):
        prev_c, prev_len = blocks[i]
        curr_c, curr_len = blocks[i + 1]
        if prev_c == '0' and curr_c == '1':
            max_k = min(prev_len, curr_len)
            for k in range(1, max_k + 1):
                valid_k.add(k)
    return len(valid_k)

# 测试示例
print(count_unique_valid_substrings("001101")) # 输出2

拓展：统计不同位置的子串数量 #

如果不需要去重，仅统计所有符合要求的子串的出现次数，直接累加每对0-1相邻块的min值即可，无需用集合存储k值，时间复杂度可优化到O(n)。

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