#include <bits/stdc++.h>
using namespace std;
const int base = 133,maxn = 2000200;
#define ull unsigned long long
int n;
string s;
stack<char> b;
map<ull,int> m;//C(2,k) = k! / 2! * (k - 2)!
ull ans,h;
ull mhash[maxn];
typedef map<ull,int>::iterator pll;//声明迭代器iterator类型
int main(){
	cin>>n;
	cin>>s;
	s = ' ' + s;
	int dep = 0;
	for(int i=1;i<=n;i++){//O(n) 求出所有字串的合法方案数 枚举原理 哈希省略了左端点的枚举
		m[h]++;//在前面统计 因为有一个continue 
		char ch = s[i];
		if(b.empty()){
			b.push(ch);
			h = h * base + ch - 'a' + 1;//加1原因 非空串不为0
			mhash[i] = h;
			dep = 0;
			continue;
		}
		if(b.top() == ch){
			b.pop();
//			h = h - (ch - 'a' + 1) / base;
			dep++;
			h = mhash[i - dep*2];//检查一下是否如此：你空字符串的哈希值是0，单独一个a的哈希值也是0 如果是，改掉。
		}else{
			b.push(ch);
			h = h * base + ch - 'a' + 1;
			dep = 0;
		}
		mhash[i] = h;
	}
	m[h]++;
	for(pll it=m.begin();it!=m.end();it++){
		int k = it->second;//C(2,k) = k! / 2! * (k - 2)!
		if(k < 2) continue;
		else if(k == 2) ans++;
		else ans += (k - 1) * k / 2;
	}
	cout<<ans;
	return 0;
}

思路：形如 abbacddc 的字符串，一个子串可消除是一个回文串，所以引入deep描述连续出栈的次数，即可消除子串的一半长度