RT，思路是暴力跳往前匹配的位置。

个人认为时间复杂度是 $O(n^2)$，但是 A 了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,ans,f[N],match[N];
string s;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s,s=' '+s;
	for(int i=1;i<=n;++i){
		if(i!=1&&s[i]==s[i-1]){
			match[i]=i-1;
			f[i]=f[i-2]+1;
			continue;
		}
		int t=i-1;
		while(match[t]>1){
			if(s[i]==s[match[t]-1]){
				match[i]=match[t]-1;
				f[i]=f[match[t]-2]+1;
				break;
			}
			t=match[t]-1;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans+=f[i];
	cout<<ans<<endl;
	return 0;
}