Algorithm

Codeforces/873B. Balanced Substring

Problem Summary

Given a string S consisting only of characters 0 and 1. A substring starts from l to r is called balanced if the number of zeroes equals to the number of ones in this substring. Determine the length of the longest balanced substring of S.

Solution

Let sum_zero[i] be the number of zeroes in the substring S[1]S[2]…S[i], and sum_one[i] be the number of ones.

If a substring S[i]S[i+1]…S[j] is balanced, we have this equation:

sum_zero[j] - sum_zero[i-1] = sum_one[j] - sum_one[i-1]   (1)

If we let diff[i] = sum_zero[i] - sum_one[i], then (1) is actually:

diff[j] = diff[i-1]   (2)

So, to find the longest substring ending at j, we only need to find the minimum i, such that (2) holds. If such i exits, the length of the longest substring ending at j is j-i+1, which can be used to update the answer.

The space and time complexities are both O(N).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100010;
int n,diff[maxn];
char s[maxn];
int min_idx[maxn*2 + 10];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	int sum0 = 0, sum1 = 0;
	memset(min_idx,-1,sizeof(min_idx));
	min_idx[maxn] = 0;
	for (int i = 1; i<=n; ++i)
	{
		if (s[i] == '0')
			++sum0;
		else
			++sum1;
		diff[i] = sum0 - sum1;
		if (min_idx[diff[i] + maxn] == -1)
			min_idx[diff[i] + maxn] = i;
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		int idx = min_idx[diff[i] + maxn];
		if (idx != -1)
			ans = max(ans,i - idx);
	}
	
	printf("%d\n",ans);
	return 0;
}