法一：
这是赛时想法。
考虑 dp。
令 \(f_i\) 表示 \(i\) 为右端点的合法子串个数，则答案为 \(\sum\limits_{i=1}^{n}f_i\)。
赛时想过匹配指针不断跳的，但当时没敢写，用了一种更直观的方法。
仿照于括号序列，合法的子串只能为 \(cAc\) 或 \(AB\)，因此找到一个最右的位置 \(l\) 使满足 \(l\sim i\) 这一段合法，然后就可以用 \(AB\) 拼接了。令 \(pre_{i,c}\) 表示前 \(i\) 个字符中，能与 \(c\) 匹配的最靠后的位置。即找到是否存在以 \(i-1\) 为右端点且满足条件的子串 \(S\)，使得 \(S\) 前面是 \(s_i\)。若有多个满足条件的 \(S\)，找到左端点最大的 \(pos\)。则 \(f_i=f_{pos-1}+1\)，因为以 \(pos-1\) 的合法子串与 \(S\) 拼起来一定合法。注意这里的 \(S\) 可能为空。
最后注意一下最后答案需要 long long。
代码：
typedef long long ll;
const int N=2e6+10;
int n;string s;ll ans;
int pre[N][26],f[N];
int main(){
cin>>n>>s;s=" "+s;
for(int i=1;i<=n;i++){
if(pre[i-1][s[i]-'a']){
int lst=pre[i-1][s[i]-'a'];
for(int j=0;j<26;j++)pre[i][j]=pre[lst-1][j];
f[i]=f[lst-1]+1;
ans+=f[i];
}
pre[i][s[i]-'a']=i;
}
cout<<ans<<"\n";
return 0;
}
法二：
看到这个像括号序列的东西，可以想到用栈，相同后弹出。
发现当两个点的栈相同时这个段一定合法，用 map 维护哈希即可。