题意回顾

给定一个只包含字符 $\texttt{a}, \texttt{b}, \texttt{c}$ 的字符串 $s$，长度 $n \le 3\times 10^5$。
求有多少个连续子串是好的——即子串中出现的各种字符的出现次数完全相同。

关键观察与转化

1. 数学表示

设子串 $s[l..r]$ 中：

• $\text{cnt}_a =$ 字符 $\texttt{a}$ 的出现次数
• $\text{cnt}_b =$ 字符 $\texttt{b}$ 的出现次数
• $\text{cnt}_c =$ 字符 $\texttt{c}$ 的出现次数

"好的"条件等价于： $\text{cnt}_a = \text{cnt}_b = \text{cnt}_c$

2. 前缀和表示

定义前缀和：

• $A[i] =$ 前 $i$ 个字符中 $\texttt{a}$ 的个数
• $B[i] =$ 前 $i$ 个字符中 $\texttt{b}$ 的个数
• $C[i] =$ 前 $i$ 个字符中 $\texttt{c}$ 的个数

对于子串 $s[l..r]$： $ \begin{aligned} \text{cnt}_a &= A[r] - A[l-1] \\ \text{cnt}_b &= B[r] - B[l-1] \\ \text{cnt}_c &= C[r] - C[l-1] \end{aligned} $

条件变为： $A[r] - A[l-1] = B[r] - B[l-1] = C[r] - C[l-1]$

3. 变量消元与差分表示

由 $A[r] - A[l-1] = B[r] - B[l-1]$ 可得： $A[r] - B[r] = A[l-1] - B[l-1]$

由 $A[r] - A[l-1] = C[r] - C[l-1]$ 可得： $A[r] - C[r] = A[l-1] - C[l-1]$

定义两个差分量： $ \begin{aligned} X[i] &= A[i] - B[i] \\ Y[i] &= A[i] - C[i] \end{aligned} $

则对于子串 $s[l..r]$，"好的"条件等价于： $X[r] = X[l-1] \quad \text{且} \quad Y[r] = Y[l-1]$

问题转化

我们需要统计满足以下条件的 $(l, r)$ 对数（$1 \le l \le r \le n$）： $X[r] = X[l-1] \quad \text{且} \quad Y[r] = Y[l-1]$

其中 $X[0] = Y[0] = 0$。

高效算法

核心思路

对于每个右端点 $r$，统计有多少个 $l-1 \in [0, r-1]$ 满足： $(X[l-1], Y[l-1]) = (X[r], Y[r])$

这可以用哈希表（或 map）来维护每个 $(X, Y)$ 状态的出现次数。

算法步骤

1. 初始化：

   • $X = 0, Y = 0$
   • $\text{cnt}[(0,0)] = 1$
   • $\text{ans} = 0$

2. 遍历右端点 $r$ 从 $1$ 到 $n$：

   • 根据 $s[r]$ 更新 $X$ 和 $Y$：
     • 若 $s[r] = \texttt{a}$：$X \gets X+1, Y \gets Y+1$
     • 若 $s[r] = \texttt{b}$：$X \gets X-1, Y$ 不变
     • 若 $s[r] = \texttt{c}$：$X$ 不变, $Y \gets Y-1$
   • $\text{ans} \ += \text{cnt}[(X, Y)]$
   • $\text{cnt}[(X, Y)] \ += 1$

正确性说明

当遇到某个 $(X, Y)$ 状态时，之前所有出现相同状态的位置 $l-1$ 都与当前 $r$ 构成"好的"子串 $s[l..r]$。
累加这些数量即得到所有以 $r$ 结尾的"好的"子串数，求和即得答案。

复杂度分析

• 时间复杂度：$O(n \cdot \text{哈希操作})$，使用 unordered_map 可达 $O(n)$
• 空间复杂度：$O(n)$，存储不同状态

总结

本题的关键在于：

1. 将"各字符出现次数相同"转化为前缀和的差分条件
2. 通过定义 $X = A-B$ 和 $Y = A-C$ 将三维条件降为二维
3. 使用哈希表统计相同状态的出现次数
4. 在线性时间内解决问题，可处理 $n \le 3\times 10^5$ 的大数据