悬关,感谢大佬!!!
若一个字符串中,所有出现的字符的数量相等,则称这个字符串为 wait 串。
给定仅含字符 l , r的字符串 s,你需要求出其中最长的 wait 串的长度。
第一行一个整数 n,表示 s 的长度。
第二行一个长度为 n 的字符串 s。
输出仅一行,即 s 中最长的 wait 串的长度。
样例输入 #1
10
lllrrlrlll
样例输出 #1
6
//85pts, 剩下15分都是WA
#include<bits/stdc++.h>
using namespace std;
long long sum[5000100];
unordered_map<long long,int> sum2;
long long n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i<=n; i++){
char p;
cin >> p;
sum[i] = sum[i-1];
if(p=='l'){
sum[i]++;
}else if(p=='r'){
sum[i]--;
}
sum2[sum[i]] = -1;
}
sum2[0] = 0;
long long ans = 0;
for(int i = 1; i<=n; i++){
//cout << ans << endl;
//cout << sum[i] << " ";
if(sum2[sum[i]]!=-1){
sum2[sum[i]] = i;
}else{
ans = max(ans,i-sum2[sum[i]]);
}
}
cout << ans;
return 0;
}