LeetCode字符串有效分割统计问题：代码提交超时原因排查与优化问询

兄弟，我看了你这段统计有效分割次数的代码，能过样例但遇上长字符串就超时，问题出在几个关键的性能瓶颈上，咱们一步步捋清楚：

原代码的性能瓶颈 #

• 子串切分+全量字符统计导致O(n²)时间复杂度：你每次循环里的string2 = s[i+1:]会创建新的字符串对象，每次操作都是O(n)时间；更糟的是，每一轮都要遍历整个string1和string2来统计不同字符，相当于每轮都做O(n)的工作，n轮下来就是O(n²)的总时间。对于长度1e5的字符串来说，1e10次操作肯定会超时。
• 重复统计完全没必要：左边的字符是逐步累加的，比如第i轮的string1是第i-1轮的结果加一个字符，你完全可以在上一轮的统计基础上更新，不用每次清空字典从头统计；右边的字符也是同理，每轮只是少了开头的一个字符，没必要每次都重新统计整个子串。

优化思路：预处理线性统计 #

咱们换个思路，提前把每个分割点的左右不同字符数算好，最后只需要遍历一次分割点计数就行，时间复杂度直接降到O(n)，完全能扛住1e5的规模：

1. 左到右统计左边字符：用一个集合记录已出现的字符，遍历字符串时每添加一个字符，就记录当前的不同字符数量到left数组——left[i]表示前i个字符（分割后左边的sleft）的不同字符数。
2. 右到左统计右边字符：同样用集合记录，反向遍历字符串，记录每个位置开始到末尾的不同字符数量到right数组——right[i]表示从第i个字符开始到末尾（分割后右边的sright）的不同字符数。
3. 遍历分割点计数：所有合法分割点是从1到len(s)-1（保证左右都非空），只要left[i] == right[i]，就把有效分割数加1。

优化后的代码 #

def numSplits(s):
    n = len(s)
    left = [0] * (n + 1)
    right = [0] * (n + 1)
    seen_left = set()
    seen_right = set()
    
    # 统计左边不同字符数
    for i in range(n):
        seen_left.add(s[i])
        left[i+1] = len(seen_left)
    
    # 统计右边不同字符数
    for i in range(n-1, -1, -1):
        seen_right.add(s[i])
        right[i] = len(seen_right)
    
    # 统计有效分割次数
    good_splits = 0
    for i in range(1, n):
        if left[i] == right[i]:
            good_splits += 1
    return good_splits

print(numSplits('aacaba'))  # 输出2，与样例一致

这个优化后的代码优势很明显：

• 全程三次线性遍历，时间复杂度O(n)，空间复杂度几乎可以忽略（因为只有小写字母，集合最多存26个元素）；
• 没有任何重复计算，每一步都是基于之前的结果累加，彻底解决了原代码里的性能问题。

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