考虑 dp，设 \(f_i\) 为以 \(i\) 结尾的合法子串个数。如果我们能对每个 \(i\)，求出来 \(g_i\) 表示最大的左端点 \(l\) 使得 \([l, i]\) 是合法串，那么 \(f_i = f_{g_i - 1} + 1\)。若 \(g_i\) 不存在则 \(f_i = 0\)。答案为 \(\sum\limits_{i = 1}^n f_i\)。
考虑求 \(g_i\)。因为 \(g_i\) 是最大的，所以 \(s_{g_i} = s_i\)，并且 \([g_i + 1, i - 1]\) 是由若干个 \([g_i, i]\) 组成的合法串拼接而成。
这启发我们连边 \(i \to g_i - 1\)，转化成求 \(i\) 不断跳出边直到跳到字符 \(s_i\) 或没有出边，并找到跳到的点。
套路地考虑倍增，设 \(F_{i, j}\) 为点 \(i\) 跳了 \(2^j\) 次出边后所在的点，\(G_{i, j}\) 为点 \(i\) 跳了 \(2^j\) 次出边后，访问过的所有点（包括 \(i\)，不包括 \(i\) 跳 \(2^j\) 次出边后所在的点），出现过的字符集合。由于 \(|\Sigma| = 26\)，因此可以用一个 int 存储。
那么求 \(g_i\) 就只用跳到最后一个点 \(j\) 使得从 \(i\) 跳到 \(j\) 都不出现字符 \(s_i\)，那么 \(j\) 往上跳一步就是我们想求的 \(g_i\)。
求出来 \(g_i\) 后，令 \(F_{i, 0} = g_i - 1, G_{i, 0} = \{s_i\}\)，再更新倍增数组即可。
有若干细节，包括要特判 \(s_{i - 1} = s_i\) 以及 \(g_i\) 不存在。
时空复杂度均为 \(O(n \log n)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2000100;
const int logn = 23;
int n, f[maxn][logn], g[maxn][logn];
ll h[maxn];
char s[maxn];
void solve() {
scanf("%d%s", &n, s + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
if (i > 1 && s[i] == s[i - 1]) {
h[i] = h[i - 2] + 1;
ans += h[i];
f[i][0] = i - 2;
g[i][0] = (1 << (s[i] - 'a'));
for (int j = 1; j < 21; ++j) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[i][j - 1] | g[f[i][j - 1]][j - 1];
}
continue;
}
int u = i - 1;
for (int j = min(__lg(i) + 1, 20); ~j; --j) {
if ((~g[u][j]) & (1 << (s[i] - 'a'))) {
u = f[u][j];
}
}
if (!u) {
g[i][0] = (1 << (s[i] - 'a'));
for (int j = 1; j < 21; ++j) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[i][j - 1] | g[f[i][j - 1]][j - 1];
}
continue;
}
--u;
h[i] = h[u] + 1;
ans += h[i];
f[i][0] = u;
g[i][0] = (1 << (s[i] - 'a'));
for (int j = 1; j < 21; ++j) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[i][j - 1] | g[f[i][j - 1]][j - 1];
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}