最后两个点MLE了，其他就过了35分

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define int long long

using namespace std;

inline int read() {
	int x=0,f=1;char s=getchar();
	while (s>'9'||s<'0') {
		if (s=='-') f=-f;
		s=getchar();
	}
	while (s>='0'&&s<='9') {
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}

const int N = 2e6+10;
const int h = 1e9+7;
const int mod = 95159089;

int n,a[N],gh[N],nxt[N],s[N],t,had,cnt[mod],ans;
char k;

signed main(){
	//freopen("random.txt","r",stdin);
	//freopen("wa.txt","w",stdout);
	n=read();
	gh[0]=1;nxt[0]=0;
	cnt[1]=1;
	for (int i=1;i<=n;++i) {
		k=getchar();
		a[i]=k-'a'+1;
		if (t>0&&a[i]==a[s[t]]) {
			gh[i]=gh[nxt[i-1]-1];
			nxt[i]=nxt[i-1]-1;
			--t;
		}
		else {
			gh[i]=gh[i-1]*h%mod;gh[i]=(gh[i]+a[i])%mod;
			nxt[i]=i;
			s[++t]=i;
		}
		//printf("gh[%d]=%d\n",i,gh[i]);
		//printf("nxt[%d]=%d\n",i,nxt[i]);
		ans-=(cnt[gh[i]]*(cnt[gh[i]]-1)/2);
		++cnt[gh[i]];
		ans+=(cnt[gh[i]]*(cnt[gh[i]]-1)/2);
		//printf("ans=%lld\n",ans);
	}
	printf("%lld\n",ans);
	return 0;
}