/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
文字列 S が与えられます．
S の各文字は，0,1,? のいずれかです．
S に含まれる全ての ? を 0 か 1 に変えて（? ごとに変換後の文字を選択できます），文字列 S' を作ることを考えます．
ここで，S' のアンバランス度を，次のように定義します．
- S' のアンバランス度 = \max \{ S' の l 文字目から r 文字目までに含まれる
0の個数と1の個数の差の絶対値 :\ 1 \leq l \leq r \leq |S|\}
S' のアンバランス度としてありうる最小の値を求めてください．
制約
- 1 \leq |S| \leq 10^6
- S の各文字は
0,1,?のいずれかである．
入力
入力は以下の形式で標準入力から与えられる．
S
出力
S' のアンバランス度としてありうる最小の値を出力せよ．
入力例 1
0??
出力例 1
1
S'=010 とすれば，アンバランス度は 1 になり，これが最小です．
入力例 2
0??0
出力例 2
2
入力例 3
??00????0??0????0?0??00??1???11?1?1???1?11?111???1
出力例 3
4
Score : 800 points
Problem Statement
Given is a string S, where each character is 0, 1, or ?.
Consider making a string S' by replacing each occurrence of ? with 0 or 1 (we can choose the character for each ? independently).
Let us define the unbalancedness of S' as follows:
- (The unbalancedness of S') = \max \{ The absolute difference between the number of occurrences of
0and1between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\}
Find the minimum possible unbalancedness of S'.
Constraints
- 1 \leq |S| \leq 10^6
- Each character of S is
0,1, or?.
Input
Input is given from Standard Input in the following format:
S
Output
Print the minimum possible unbalancedness of S'.
Sample Input 1
0??
Sample Output 1
1
We can make S'= 010 and achieve the minimum possible unbalancedness of 1.
Sample Input 2
0??0
Sample Output 2
2
Sample Input 3
??00????0??0????0?0??00??1???11?1?1???1?11?111???1
Sample Output 3
4