统计以A开头B结尾的子串：右向左遍历优化暴力算法技术问询

嘿，这个问题我之前刷算法题的时候刚好琢磨过，咱们先把事儿说透，再聊优化的思路和优势～

暴力思路确实够直观：碰到每个'A'就往后扫所有'B'，找到一个就给计数加1。但问题也很明显——时间复杂度是O(n²)，比如如果字符串是AAAAA...BBBBB（前半段全A，后半段全B），那每个A都要扫一遍所有B，总操作次数是(n/2)*(n/2)，数据量一大（比如n=1e5），直接就卡爆了。

其实换个方向想：我们要的是「每个A右边的B的数量之和」，那干嘛不反过来遍历，提前记好已经遇到的B的数量？

具体步骤超简单：

• 初始化两个变量：total（存最终结果）和b_count（记录已经遇到的B的数量）
• 从字符串的最后一个字符开始往左遍历：
  • 如果当前字符是'B'：把b_count加1（因为这个B可以被左边的A配对）
  • 如果当前字符是'A'：把当前的b_count加到total里（这个A能和所有已经统计过的B组成符合要求的子串）
  • 其他字符直接忽略就行

给你写个Python的实现示例，一看就懂：

def count_ab_substrings(s):
    total = 0
    b_count = 0
    # 反向遍历字符串
    for char in reversed(s):
        if char == 'B':
            b_count += 1
        elif char == 'A':
            total += b_count
    return total

# 测试示例里的字符串
test_str = "CABAAXBYA"
print(count_ab_substrings(test_str))  # 输出4，和示例完全一致

• 时间复杂度直接降到O(n)：不管字符串是什么结构，只需要遍历一次，线性时间复杂度，大数据量下的性能提升不是一点半点。比如n=1e6的时候，暴力解法要做5e11次操作，优化后只需要1e6次，完全不在一个量级。
• 空间复杂度O(1)：只用到两个变量，不需要额外的数组、哈希表之类的存储空间，内存开销极小。
• 逻辑更简洁，不易出错：没有嵌套循环，不用处理内层循环的边界问题，代码写起来快，调试也简单。

本质是抓住了问题的核心：每个符合要求的子串，都是一个A加上它右边的某个B。所以我们只需要在遍历到A的时候，知道它右边有多少个B——反向遍历刚好能让我们提前统计好右边的B的数量，遇到A直接累加就行，完美命中需求。

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