📝 题目大意

给定长度为 $N$ 的字符串 $S$，定义 $S_i$ 为删除 $S$ 的第 $i$ 个字符后得到的字符串。求有多少对 $(i,j)$ 满足 $1 \leq i < j \leq N$ 且 $S_i = S_j$。

💡 解题思路

1. 题目分析：考虑 $S_i$ 与 $S_j$（设 $i < j$）何时相等。逐字符比对：

   • 对于 $k < i$：$S_i[k] = S_k$，$S_j[k] = S_k$，自然相等。
   • 对于 $i \leq k < j$：$S_i[k] = S_{k+1}$，$S_j[k] = S_k$。要使二者相等，需要 $S_{k+1} = S_k$ 对所有 $k \in [i, j-1]$ 成立。
   • 对于 $k \geq j$：$S_i[k] = S_{k+1}$，$S_j[k] = S_{k+1}$，自然相等。

   因此 $S_i = S_j$ 当且仅当 $S_i = S_{i+1} = \cdots = S_j$，即 $i$ 和 $j$ 落在 $S$ 的同一个连续相等字符段（run）内。

2. 算法推导：将 $S$ 划分为若干"极大连续相等字符段"。对于长度为 $len$ 的段，其中任意两个不同位置 $(i, j)$ 都满足 $S_i = S_j$，贡献为组合数 $C(len, 2) = \frac{len \cdot (len-1)}{2}$。遍历字符串，维护变量 a 记录当前连续相等字符的个数：

   • 若 $S_{i-1} = S_i$，则 a++（当前段延续）；
   • 否则，将当前段的贡献 $\frac{a(a-1)}{2}$ 累加到答案 x，并重置 a = 1（开始新的一段）。
   • 遍历结束后，别忘了加上最后一段的贡献。

3. 边界与细节：

   • $N \geq 2$，不存在空串情况。
   • 答案可能很大：最坏情况 $N = 3 \times 10^5$ 且全部相同字符，答案为 $\frac{N(N-1)}{2} \approx 4.5 \times 10^{10}$，超过 32 位 int 范围，必须使用 long long（std.cpp 中 n、a、x 均为 long long）。
   • 当 $a = 1$ 时，$\frac{a(a-1)}{2} = 0$，无需特殊处理。

⏱️ 复杂度分析

• 时间复杂度：仅需一次线性扫描，$O(N)$。
• 空间复杂度：仅使用常数个变量，$O(1)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n, a = 1, x = 0;  // n: 字符串长度, a: 当前连续相等段长度, x: 答案
    string s;
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == s[i])
            a++;                // 当前段延续，长度+1
        else {
            x += a * (a - 1) / 2; // 段结束，累加 C(a, 2)
            a = 1;                // 重置为新段
        }
    }
    x += a * (a - 1) / 2;        // 处理最后一段的贡献
    cout << x;
}