字符串连续子串不同字符集计数的代码排错与优化

问题说明 #

题目要求统计给定字符串的所有连续子串中，互不重复的字符集合总数量。
以字符串"abbc"为例：

• 全部连续子串为：a、ab、abb、abbc、b、bb、bbc、bc、c
• 各子串去重后的字符集合为：{a}、{a,b}、{a,b}、{a,b,c}、{b}、{b}、{b,c}、{b,c}、{c}
• 去重后共6个不同集合，即答案为6

原代码问题定位 #

你写的暴力枚举逻辑本身没有错误：

1. 双层循环枚举所有连续子串的逻辑正确，切片范围a[i:j+1]覆盖了所有可能的连续非空子串
2. 用frozenset存储字符集合作为字典key的用法正确，frozenset是可哈希类型，能准确区分不同字符集合
3. 用示例"abbc"测试你的代码，输出结果为6，和预期完全一致
4. 测试数组中第二个字符串qejyogmmtlmgqzi的运行结果75和预期完全匹配，也能验证逻辑正确性

结果不匹配的原因是：你代码中arr列表里的部分测试字符串和原题输入不一致，存在字符漏写、错写或者重复字符多写/少写的问题，重新核对复制原题的输入字符串即可得到正确结果。

代码优化方案 #

你的原代码是朴素暴力解法，时间复杂度为O(n²)，当字符串长度较大时（比如长度超过1000）运行效率会很低。由于题目中的字符都是小写英文字母，总共只有26种，可以用位掩码+滚动集合的方案把时间复杂度降到O(n*26)，效率提升非常明显：

优化思路 #

• 用整数的二进制位表示字符集合：比如第0位为1代表包含字符a，第1位为1代表包含字符b，以此类推，一个整数即可唯一表示一个字符集合，比frozenset运算速度快很多
• 滚动维护以当前位置结尾的所有不同字符集合：处理第i位字符时，以i结尾的所有子串的字符集合，等于「以i-1结尾的所有字符集合都加上当前字符」，再加上「仅包含当前字符的集合」，去重后就是当前位置的所有有效集合
• 每一步得到的集合都加入全局结果集，最后全局结果集的大小就是答案
• 由于最多只有26种字符，每个位置维护的不同集合数量最多为26个，不会随字符串长度增长

优化后代码 #

arr =['wpcbgphrbqspegjo','qejyogmmtlmgqzi','wroyjvcaiallyshhspfy','qvjiayljivsei','auxpaufisazsdpcpkzz','qdyvxihsmwwyit','ejmmxvrkxb','rapbkfkvgyka','hrklzzudfh','hhmzxkpdgehxjgrmgjex']

for s in arr:
    total_sets = set()
    # prev 存储以上一个位置结尾的所有不同字符集合（位掩码形式）
    prev = set()
    for c in s:
        bit = 1 << (ord(c) - ord('a'))
        curr = set()
        # 上一轮的所有集合都加上当前字符
        for mask in prev:
            curr.add(mask | bit)
        # 加上仅包含当前字符的集合
        curr.add(bit)
        # 把当前轮的集合加入全局结果
        total_sets.update(curr)
        # 更新prev为当前轮的集合，供下一轮使用
        prev = curr
    print(len(total_sets))

注意：运行前请先核对arr列表中的字符串和原题输入完全一致，否则结果依然会有偏差。

内容的提问来源于stack exchange，提问作者SAI SANTOSH CHIRAG