题意描述
有一个字符串, 请你求出有多少个字串可以经过若干次, 使它变成空串
其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。
## 思路1
可以枚举左端点, 再枚举右端点, 一边枚举一边判断是否合法
时间复杂度 $O(n^2)$
空间复杂度 $O(n)$
## 思路2
我们可以看出, 如果一个字串可以删除， 那么这一段可以完全抵消, 令这个字串的左端点为 $l$, 右端点为 $r$, 所以从 $1$ ~ $l - 1$ 和从 $1$ ~ $r$的栈是相同的(因为从 $l$ ~ $r$ 这一段的都被抵消了)可以用前缀和维护从 $1$ ~ $i$的栈出现数量, 再哈希统计答案
时间复杂度 $O(n \log n)$
空间复杂度 $O(n \log n)$
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
unordered_map<unsigned long long, int>t;
unsigned long long wei[N];
string o;
int n;
unsigned long long ok;
char c;
long long ans;
int tot;
int main(){
cin >> n;
wei[0] = 1;
for(int i = 1; i <= 1000000; i++){
wei[i] = wei[i - 1] * 13331;
}
ok = 0;
t[0] = 1;
for(int i = 1; i <= n; ++i){
cin >> c;
if(o.size() && o[o.size() - 1] == c){
ok -= (o[o.size() - 1] - 'a' + 1) * wei[int(o.size())];
o.pop_back();
}
else{
o += c;
ok += (c - 'a' + 1) * wei[int(o.size())];
}
t[ok]++;
ans += t[ok] - 1;
}
cout << ans;
return 0;
}