如何高效计算字符串中字符频率的前缀和？（附示例）

嘿，这个问题问到点子上了！计算字符频率的前缀和关键就是别做重复劳动——要是每次都从字符串开头重新统计到当前位置，那长字符串下来效率会低得离谱。咱们就用你给的例子s = 'AAABBBCAB'来一步步讲最高效的实现思路。

核心思路：增量更新+保存副本 #

前缀和数组里的每一项，其实都是前一项的计数结果加上当前字符的增量。所以我们只需要维护一个「当前计数」的容器，每遍历一个字符就更新它，然后把这个容器的副本存到前缀和列表里就行。这样整个过程只需要遍历字符串一次，时间复杂度是O(n)，绝对是最高效的方式。

Python 实现（字典版，和你的示例格式完全匹配） #

直接上代码，注释里写清楚每一步：

s = 'AAABBBCAB'
prefix_sums = []
current_counts = {}

for char in s:
    # 更新当前字符的计数：如果字符不在字典里就设为1，否则加1
    current_counts[char] = current_counts.get(char, 0) + 1
    # 必须存副本！如果直接存current_counts的引用，后面修改会影响之前所有项
    prefix_sums.append(current_counts.copy())

# 输出验证结果，和你要的完全一致
for item in prefix_sums:
    print(item)

运行这段代码后，得到的prefix_sums就是你给出的psum数组，完美匹配。

优化方案：用数组代替字典（字符集有限时） #

如果你的字符串里的字符是固定范围的（比如只有大写英文字母、小写字母或者数字），用数组代替字典会更快——数组的索引访问比字典的哈希查找开销更小。比如针对大写字母的情况：

s = 'AAABBBCAB'
prefix_sums = []
# 初始化26个0，对应A-Z的计数
current_counts = [0] * 26

for char in s:
    # 把字符转成数组索引：A对应0，B对应1...
    idx = ord(char) - ord('A')
    current_counts[idx] += 1
    # 复制数组存入前缀和
    prefix_sums.append(current_counts.copy())

# 如果需要转成字典格式，加个小函数处理就行
def counts_to_dict(counts_arr):
    return {chr(ord('A') + i): cnt for i, cnt in enumerate(counts_arr) if cnt > 0}

# 转换后的结果和字典版完全一致
dict_prefix_sums = [counts_to_dict(item) for item in prefix_sums]
for item in dict_prefix_sums:
    print(item)

这种方式在处理超长字符串时，性能会比字典版略优一点。

为啥这是高效的？ #

对比一下低效的做法：比如对每个位置i，都从s[0]到s[i]重新统计频率，这样时间复杂度是O(n²)——n是字符串长度，当n很大（比如10^5级别）时，这种方法会直接卡爆。而我们的增量更新法只需要O(n)的时间，空间复杂度也是O(n*k)（k是不同字符的数量），这是无法避免的，毕竟要保存每一步的结果。

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