考场上10min弄了个哈希。

#include <bits/stdc++.h>
using namespace std;
unordered_map<string,long long>mp;
int n;
long long ans;
string s,ss="";
int main()
{
	scanf("%d",&n);
	cin>>s;
	mp[""]=1;
	for(int i=0;i<n;i++)
	{
		if(!ss.empty()&&s[i]==ss.back())
			ss.pop_back();
		else
			ss.push_back(s[i]);
		ans+=mp[ss];
		mp[ss]++;
	}
	printf("%lld",ans);
}

我这个代码理论复杂度是 $\mathcal{O(n^2)}$ 的吗？为什么能跑过 2e6？unordered_map 常数大不大？

提交记录