题解

思路

对 $i<j$ 比较 $S_i$ 与 $S_j$：删除位置以前和位置 $j$ 以后本来就相同，中间部分相等当且仅当原串的 $S_i,S_{i+1},\ldots,S_j$ 全部相同。

做法

因此，一个合法位置对恰好是同一个相同字符连续段内任选两个位置。若某段长度为 $len$，它贡献 $\binom{len}{2}=len(len-1)/2$ 个位置对。

线性扫描字符串，遇到字符变化时结算上一段并开始新段，最后再结算末段即可。答案最大约为 $N^2/2$，需要使用 64 位整数。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。