记 数组a 是记录“0”的前缀和个数,数组b 是记录“1”的前缀和个数,如果一段区间[i, j]是平衡串的话,说明该区间的0和1的数量相同,则a[j] - a[i - 1] = b[j] - b[i - 1],
化简为:a[j] - b[j] = a[i - 1] - b[i - 1]
a[j] - b[j]就是前缀和长度为j的 0 和 1 的个数之差,记为s[j],化简式子就是:c[j] = c[i - 1],所以用哈希表存储每段区间的差值,然后找相同的差值的点(相同的差值就说明该区间是平衡串,由前面推导而来),两个点就构成区间,最后遍历整个字符串,求出最长平衡串
时间复杂度O(n)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 10;
char s[N];
unordered_map<int, int> p;
int a[N], b[N], c[N];
int n;
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i ++ )
{
a[i] = a[i - 1], b[i] = b[i - 1];
if (s[i] == '0') a[i] ++ ;
else b[i] ++ ;
c[i] = a[i] - b[i];
}
p[0] = 0;
int res = 0;
for (int i = 1; i <= n; i ++ )
if (p.count(c[i]) == 0) p[c[i]] = i;
else res = max(res, i - p[c[i]]);
cout << res << endl;
return 0;
}