B. Balanced Substring time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You are given a string?s?consisting only of characters?0?and?1. A substring?[l,?r]?of?s?is a string?slsl?+?1sl?+?2...?sr, and its length equals to?r?-?l?+?1. A substring is called?balanced?if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest?balanced?substring of?s.

Input

The first line contains?n?(1?≤?n?≤?100000) — the number of characters in?s.

The second line contains a string?s?consisting of exactly?n?characters. Only characters?0?and?1?can appear in?s.

Output

If there is no non-empty?balanced?substring in?s, print?0. Otherwise, print the length of the longest?balanced?substring.

Examples input 8 11010111 output 4 input 3 111 output 0 Note

In the first example you can choose the substring?[3,?6]. It is?balanced, and its length is?4. Choosing the substring?[2,?5]?is also possible.

In the second example it's impossible to find a non-empty?balanced?substring.

題解：a[i]表示的是[0..i]區(qū)間內(nèi)1和0的個數(shù)之差。

如果a[i]==a[j]的話，那么[i+1,j]區(qū)間1和0的數(shù)量相同。

確定下每個a[i]出現(xiàn)的最早下標(biāo)和最晚下標(biāo)，做差一下，然后更新答案即可。

代碼：

#include <bits/stdc++.h> using namespace std; int n,x,k; const int maxn = 100010; int a[maxn]; map<int,int> mark; int main(){cin>>n;int nums = 0;for(int i = 1;i <= n;++i){char c;scanf(" %c",&c);if(c == '0') nums--;else nums++;a[i] = nums;if(!mark[nums]) mark[nums] = i;}mark[0] = 0;int ans = 0;for(int i = 1;i <= n;++i){ans = max(ans,i - mark[a[i]]);}cout<<ans<<endl; }

總結(jié)

以上是生活随笔為你收集整理的codeforces Balanced Substring的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。