AcWing 3553. 最长平衡串
原题链接
简单
作者:
小.bug
,
2022-08-10 20:29:39
,
所有人可见
,
阅读 448
/*
a[i]表示前i个字符1的个数,b[i]表示前i个字符0的个数
假设【i+1, j】这一子串满足1的个数和0的个数相等
所以可知a[j] - a[i] == b[j] - b[i]
移项整理可知a[j] - b[j] == a[i] - b[i]
设c[i] = a[i] - b[i]
所以可得:当c[i] == c[j]时,【i+1, j】这一子串满足1的个数和0的个数相等
所以求最长平衡串只需用哈希表记录每一个c[i]值出现的第一次位置即可
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
char str[N];
int a[N], b[N], c[N];
unordered_map<int, int> h;
int main()
{
cin >> str + 1;
int n = strlen(str + 1);
for(int i = 1; i <= n; i ++)
{
a[i] = a[i - 1] + (str[i] - '0'); //前i个字符中1的个数
b[i] = i - a[i]; //前i个字符中0的个数
c[i] = a[i] - b[i];
}
h[0] = 0;
int res = 0;
for(int i = 1; i <= n; i ++)
{
if(!h.count(c[i])) h[c[i]] = i; //哈希表中没有c[i],所以c[i]的值第1次出现
else res = max(res, i - h[c[i]]);
}
cout << res << endl;
return 0;
}