ZYB loves binary strings (strings that only contains
1’). And he loves equal binary strings more, where the number of
0and the number of
1 in the string are equal.
ZYB wants to choose a substring from an original string
T so that it is an equal binary stringwith the longest length possible. He also wants to choose a subsequence of
T which meets the same requirements.
v is a substring of a string
v is empty, or there are two integers
r (1≤l≤r≤∣w∣) such that
v=wl*wl+1 ⋯wr A string v is a subsequence of a string
w if it can be derived from w by deleting any number (including zero) of characters without changing the order of the remaining characters.
For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.
The first line of the input contains a single integer
N≤100000)，the length of the original string
T. The second line contains a binary string with exactly
Ncharacters, the original string
Print two integers
B, denoting the answer for substring and subsequence respectively.
设s1[i]为前i项0的个数，s2[i]为前i项1的个数，所以[i,j]范围内有0 s1[j]-s1[i-1]个，1 s2[j]-s2[i-1]个。
s1[j]-s1[i-1] = s2[j]-s2[i-1]
s1[j]-s2[j] = s1[i-1] - s2[i-1]
设x[i] = s1[i] - s2[i]
得到当x[j] = x[i-1] 时 满足情况。
写一个结构体，重新排序一下，然后取 x[j]=x[i-1] 的情况即可（此方法适用于各种前缀和N^2 TLE 求子串含有相同字符的时候）