求首尾字符不同的字符串子串数量（重复子串重复计数）及优化思路

直接枚举所有子串判断首尾字符的方法时间复杂度为O(n²)，长字符串下效率极低，更优的思路是通过反向减法快速求解：

步骤1：计算总子串数 #

对于长度为n的字符串，总子串数的计算公式为：

总子串数 = n * (n + 1) // 2

逻辑是：每个起始位置i（0到n-1）可对应n - i个结尾位置，累加所有起始位置的可能数，等价于求1到n的和。

步骤2：计算首尾字符相同的子串数 #

这部分由两部分相加得到：

• 单个字符的子串：共n个，每个子串的首尾字符必然相同。
• 长度≥2的首尾相同子串：统计每个字符在字符串中的出现次数k，对每个字符计算组合数k * (k - 1) // 2，再将所有字符的结果求和。这个组合数的含义是：从该字符的k个出现位置中选两个位置（前一个作为子串起始，后一个作为结尾），每个组合对应一个首尾相同的长串。

首尾相同子串总数 = n + sum(k*(k-1)//2 for 每个字符的出现次数k)

步骤3：计算目标结果 #

首尾字符不同的子串数 = 总子串数 - 首尾相同子串数

示例验证 #

以字符串"abac"为例：

• 字符串长度n=4，总子串数=4*5//2=10
• 首尾相同子串数：单个字符4个，字符a出现2次，对应组合数2*1//2=1；b和c各出现1次，组合数为0。总和=4+1=5
• 首尾不同子串数=10-5=5，与实际枚举结果一致。

实现细节 #

• 用哈希表（如Python的dict）或固定大小的数组（若字符集为有限范围，比如小写英文字母）统计每个字符的出现次数，遍历一次字符串即可完成统计，时间复杂度O(n)。
• 所有计算均为O(1)算术操作，整体时间复杂度为O(n)，空间复杂度为O(1)（字符集有限时）或O(k)（k为不同字符的数量），远优于暴力枚举的O(n²)。

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