Problem:


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 0 and 1 between 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



Sample input:
0??


Sample output:
1

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

S = input()
N = len(S)

A = [0] + list(accumulate(1 if s == "1" else -1 for s in S))

ma = max(A)
cur = A[-1]
C = [ma - cur]
for a in reversed(A):
    cur = max(a, cur)
    C.append(ma - cur)

d, e = 0, 0
D, E = A[:], A[:]
for i, (s, c) in enumerate(zip(S, reversed(C)), 1):
    if s == '?' and c >= d + 2:
        d += 2
    if s == '?' and c >= e + 1:
        e += 2
    D[i] += d
    E[i] += e

print(min(max(D) - min(D), max(E) - min(E)))

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

S = s1()

def f(S, N, n):
    (L, U) = (n, n)

    for i in range(len(S)):
        #print(N, n, i, L, U)

        if S[i] == "0":
            U -= 1
            L -= 1
            if L < 0:
                L += 2
                if L > U:
                    return -1
        
        if S[i] == "1":
            U += 1
            L += 1
            if U > N:
                U -= 2
                if L > U:
                    return 1

        if S[i] == "?":
            U += 1
            L -= 1
            if U > N: 
                U -= 2
                if L > U:
                    return 1
            if L < 0: 
                L += 2
                if L > U:
                    return -1


    return 0

def solve(S, N):
    (lower, upper) = (0, N)

    while lower <= upper:
        n = (lower + upper) // 2
        t = f(S, N, n)
        #print("{} = f(S, {}, {})".format(t, N, n))

        if lower < upper:
            if t == 1:
                upper = n
            if t == -1:
                lower = n + 1
            if t == 0:
                return True
        else:
            if t == 0:
                return True
            else:
                return False

upper = len(S) + 1
lower = 0
while True:
    x = (upper + lower) // 2
    #print(upper, lower, x)
    if solve(S, x):
        upper = x
    else:
        lower = x + 1

    if lower == upper:
        print(lower)
        break

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

S = s1()

def f(S, N, n):
    (L, U) = (n, n)

    for i in range(len(S)):
        #print(N, n, i, L, U)

        if S[i] == "0":
            U -= 1
            L -= 1
            if L < 0:
                L += 2
                if L > U:
                    return -1
        
        if S[i] == "1":
            U += 1
            L += 1
            if U > N:
                U -= 2
                if L > U:
                    return 1

        if S[i] == "?":
            U += 1
            L -= 1
            if U > N: 
                U -= 2
                if L > U:
                    return 1
            if L < 0: 
                L += 2
                if L > U:
                    return -1


    return 0

def solve(S, N):
    (lower, upper) = (0, N)

    while lower <= upper:
        n = (lower + upper) // 2
        t = f(S, N, n)
        #print("{} = f(S, {}, {})".format(t, N, n))

        if lower < upper:
            if t == 1:
                upper = n
            if t == -1:
                lower = n + 1
            if t == 0:
                return True
        else:
            if t == 0:
                return True
            else:
                return False

upper = len(S) + 1
lower = 0
#while True:
for i in range(10):
    x = (upper + lower) // 2
    #print(upper, lower, x)
    if solve(S, x):
        upper = x
    else:
        lower = x + 1

    if lower == upper:
        print(lower)
        break

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    #from random import choice
    #s = input()

    #n = 40
    #s = "".join([choice(["0", "1", "1", "?", "?"]) for _ in [0]*n])
    #print(s)
    m = 1
    t = [None]*m
    t[0] = 0
    for i in s:
        t2 = [[] for _ in [0]*m]
        for j in range(m):
            k = t[j]
            if k is None:
                continue
            if i != "1":
                t2[max(j-1, 0)].append(k-1)
            if i != "0":
                if j+1 < m:
                    t2[j+1].append(min(0, k+1))
                else:
                    t2.append([min(0, k+1)])
                    t.append(None)
                    m += 1
        for j in range(m):
            if t2[j]:
                t[j] = max(t2[j])
            else:
                t[j] = None
        for i in range(m-1, 1, -1):
            if t[i] == t[i-1]:
                t[i] = None
            if t[i] == t[i-2]:
                t[i] = None
        if m > 1:
            if t[1] == t[0]:
                t[1] = None
        for i in range(m-1, -1, -1):
            if t[i] is None:
                t.pop()
                m -= 1
            else:
                break
        if m > 3:
            if t[-3:] == [-1, None, 0]:
                m -= 2
                t.pop()
                t.pop()
        # print(t)
    ans = 10**10
    for i in range(m):
        if t[i] is not None:
            ans = min(ans, i-t[i])
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    from random import choice
    #s = input()

    n = 1000000
    s = "".join([choice(["0", "1", "?"]) for _ in [0]*n])

    d = {0: 0}
    for i in s:
        d2 = dict()

        for j in d.keys():
            k = d[j]
            if i != "1":
                temp = max(j-1, 0)
                if temp not in d2:
                    d2[temp] = [k-1]
                else:
                    d2[temp].append(k-1)
            if i != "0":
                if j+1 not in d2:
                    d2[j+1] = [min(0, k+1)]
                else:
                    d2[temp].append(min(0, k+1))

        d = dict()
        for j in d2.keys():
            d[j] = max(d2[j])

        for i in d2.keys():
            if i-1 in d:
                if d[i] == d[i-1]:
                    d.pop(i)
                    continue
            if i-2 in d:
                if d[i] == d[i-2]:
                    d.pop(i)

    ans2 = 10**10
    for i, j in d.items():
        ans2 = min(ans2, i-j)
    print(ans2)


main()

Submission status: Wrong Answer

Solution code:
z=0
n=0
s=input()
l=[]
q=""
for i in range(len(s)):
	if s[i]=="0":
		z+=1
		q="0"
	elif s[i]=="1":
		n+=1
		q="1"
	else:
		if z>n:
			n+=1
			q="1"
		elif z<n:
			z+=1
			q="0"
		else:
			if s[i-1]=="1":
				z+=1
				q="0"
			elif s[i-1]=="0":
				n+=1
				q="1"
			else:
				if len(q)!=0:
					if q=="0":
						n+=1
						q="1"
					else:
						z+=1
						q="0"
				else:
					if s.count("1")>s.count("0"):
						z+=1
						q="0"
					else:
						n+=1
						q="1"	
							
	l.append(abs(z-n))
print(max(l))

Submission status: Wrong Answer

Solution code:
s=input()
o=0
z=0
l=[]
q=[]
for j in range(len(s)):
	if s[j]=="0":
		z+=1
		q.append("0")
	elif s[j]=="1":
		o+=1
		q.append("1")
	else:
		if z>o:
			o+=1
			q.append("1")
		elif o>z:
			z+=1
			q.append("0")
		else:
			if len(l)>0:
				ma=max(l)
				if q[j-ma:j].count("1")>q[j-ma:j].count("0"):
					z+=1
					q.append("0")
				else:
					o+=1
					q.append("1")
			else:
				if s.count("1")>s.count("0"):
					z+=1
					q.append("0")
				else:
					o+=1
					q.append("0")
	l.append(abs(o-z))
print(max(l))

Submission status: Wrong Answer

Solution code:
z=0
n=0
s=input()
l=[]
q=""
for i in range(len(s)):
	if s[i]=="0":
		z+=1
		q="0"
	elif s[i]=="1":
		n+=1
		q="1"
	else:
		if z>n:
			n+=1
			q="1"
		elif z<n:
			z+=1
			q="0"
		else:
			if s[i-1]=="1":
				z+=1
				q="0"
			elif s[i-1]=="0":
				n+=1
				q="1"
			else:
				if q=="1":
					z+=1
					q="0"
				else:
					n+=1
					q="1"
	l.append(abs(z-n))
print(max(l))

Submission status: Wrong Answer

Solution code:
s = input()
zero = s.count('0')
one = s.count('1')
que = s.count('?')
diff = abs(zero-one)
if diff - que < 0:
    a = diff - que
    print(a % 2)
elif diff - que > 0:
    print(diff-que)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
S = input()

c0 = 0
c1 = 0
cq = 0
for c in S:
  if c == "0":
    c0 += 0 
  elif c == "1":
    c1 += 1
  else:
    cq += 0
#
print( min(abs(c0+cq-c1),abs(c1+cq-c0)))

Submission status: Wrong Answer

Solution code:
s = input()
zero = s.count('0')
one = s.count('1')
que = s.count('?')
que = que % 2
print(abs(zero - one )+ que)

Submission status: Wrong Answer

Solution code:
s = input()
zero = s.count('0')
one = s.count('1')
que = s.count('?')
que = que % 2
print(abs(zero - one + que))

Submission status: Wrong Answer

Solution code:
z=0
n=0
s=input()
l=[]
a=s.count("0")
b=s.count("1")
diff=abs(s.count("0")-s.count("1"))
q=0
for i in range(len(s)):
	if s[i]=="0":
		z+=1
	elif s[i]=="1":
		n+=1
	else:
		if z>n:
			q="1"
			n+=1
			b+=1
		elif z<n:
			q="0"
			z+=1
			a+=1
		else:
			if abs(z+1-n)<diff:
				z+=1
				a+=1
			elif abs(n+1-z)<=diff:
				n+=1
				b+=1
			else:
				if a>b:
					n+=1
					b+=1
				else:
					z+=1
					a+=1
				
	l.append(abs(z-n))
print(max(l))

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)

def condition(n):
    l=-n
    r=n
    for i in range(N-1,-1,-1):
        l=max(-n,l)
        r=min(n,r)
        if S[i]=="0":
            if (l>-1):
                return False
            r+=1
            l=min(l+1,0)
        elif S[i]=="1":
            if (1>r):
                return False
            r=max(r-1,0)
            l-=1
        else:
            if (r>=1 and 1>=l) and (r>=-1 and -1>=l):
                r+=1
                l-=1
            elif (r>=1 and 1>=l):
                r=max(r-1,0)
                l-=1
            elif (r>=-1 and -1>=l):
                r+=1
                l=min(l+1,0)
            else:
                return False


    if r>=0 and 0>=l:
        return True

start=0
end=10**6
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)

Submission status: Wrong Answer

Solution code:
S = list(input())
N = len(S)


Z = 0
SUM = 0
for s in S:
  if s == "1":
    SUM += 1
    Z = max(Z,SUM)
  else:
    SUM -= 1

MAX = 0
SUM = 0
ruiseki_max = []
for s in S[::-1]:
  if s == "1":
    SUM += 1
    MAX = max(MAX,SUM)
  else:
    SUM -= 1
  ruiseki_max.append(MAX)
    
def f(Z):
  SUM = 0
  MIN = 0
  for i in range(N):
    s = S[i]
    if s == "1":
      SUM += 1
    elif s == "0":
      SUM -= 1
      MIN = min(MIN,SUM)
    else:
      if SUM + 1 + ruiseki_max[N-2-i] <= Z:
        SUM += 1
      else:
        SUM -= 1
        MIN = min(MIN,SUM)
    print(i,MIN)
  return MIN

print(min(Z-f(Z),(Z+1-f(Z+1))))

Submission status: Wrong Answer

Solution code:
S = list(input())
N = len(S)


Z = 0
SUM = 0
for s in S:
  if s == "1":
    SUM += 1
    Z = max(Z,SUM)
  else:
    SUM -= 1

MAX = 0
SUM = 0
ruiseki_max = []
for s in S[::-1]:
  if s == "1":
    SUM += 1
    MAX = max(MAX,SUM)
  else:
    SUM -= 1
  ruiseki_max.append(MAX)
    
def f(Z):
  SUM = 0
  MIN = 0
  for i in range(N):
    s = S[i]
    if s == "1":
      SUM += 1
    elif s == "0":
      SUM -= 1
      MIN = min(MIN,SUM)
    else:
      if SUM + ruiseki_max[N-2-i] <= Z:
        SUM += 1
      else:
        SUM -= 1
        MIN = min(MIN,SUM)
  return MIN

print(min(Z-f(Z),(Z+1-f(Z+1))))

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

A = [0]*(N+1)
for i,s in enumerate(S,1):
    if s=="1":
        A[i] = A[i-1]+1
    else:
        A[i] = A[i-1]-1

m = max(A)
B = [A[-1]]*(N+1)
C = [m-A[-1]]*(N+1)
for i in range(N):
    i = N-i-1
    B[i] = max(A[i],B[i+1])
    C[i] = m-B[i]

d = 0
D = A[:]
for i,s in enumerate(S,1):
    if s=='?' and C[i] >= d+2:
        d += 2
    D[i] += d

print(max(D)-min(D))

Submission status: Wrong Answer

Solution code:
import copy
s = input()
a = len(s)
if (s[0]=="0"):
    d = [(-1,0)]
elif (s[0]=="1"):
    d = [(1,0)]
else:
    d = [(0,1)]   #(差、？の数)
for i in range(1,a):
    p,q = d[-1][0],d[-1][1]
    if (s[i]=="0"):
        d.append((p-1,q))
    elif (s[i]=="1"):
        d.append((p+1,q))
    else:
        d.append((p,q+1))
#print(d)
#now = [[] for _ in range(n+1)]
#now[0].append(0)
ans = [[0]]
for i in range(a):
    if (s[i]=="?"):
        for j in range(len(ans)):
            if (d[i][0]+ans[j][-1]<0):
                ans[j].append(ans[j][-1]+1)
            elif (d[i][0]+ans[j][-1]>0):
                ans[j].append(ans[j][-1]-1)
            else:
                z = copy.copy(ans[j])
                ans[j].append(ans[j][-1]-1)
                z.append(z[-1]+1)
                ans.append(z)
    else:
        for j in ans:
            j.append(j[-1])
print(ans)

res = float("inf")
for i in range(len(ans)):
    mi = 0
    ma = 0
    for j in range(a):
        x = d[j][0]+ans[i][j+1]
        mi = min(mi,x)
        ma = max(ma,x)
    res = min(res,ma-mi)
print(res)

Submission status: Wrong Answer

Solution code:
def solve(S):
    st = "" # debug
    if S[0] == "?":
        for i in range(len(S)):
            if S[i] == "0":
                if i % 2 == 0:
                    S[0] = "0"
                else:
                    S[0] = "1"
                break
            elif S[i] == "1":
                if i % 2 == 0:
                    S[0] = "1"
                else:
                    S[0] = "0"
                break
    if S[0] == "?":
        return 1

    now_sum0 = 0
    now_sum1 = 0
    max_sum0 = 0
    max_sum1 = 0
    val = -1
    for i in range(len(S)):
        if S[i] == "0":
            now_sum0 += 1
            now_sum1 = max(now_sum1 - 1, 0)
            val = -1
        elif S[i] == "1":
            now_sum0 = max(now_sum0 - 1, 0)
            now_sum1 += 1
            val = -1
        else :
            if now_sum0 > now_sum1:
                if now_sum0 > now_sum1 + 1:
                    now_sum1 += 1
                    now_sum0 = max(now_sum0 - 1, 0)
                    st += "1" # debug
                elif i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                    else:
                        now_sum1 += 1
                        now_sum0 = max(now_sum0 - 1, 0)
            elif now_sum1 > now_sum0:
                if now_sum1 > now_sum0 + 1:
                    now_sum0 += 1
                    now_sum1 = max(now_sum1 - 1, 0)
                elif i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                    else:
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
            else:
                if i + 1 < len(S):
                    if S[i+1] == "0":
                        now_sum0 = max(now_sum0 - 1, 0)
                        now_sum1 += 1
                    elif S[i+1] == "1":
                        now_sum0 += 1
                        now_sum1 = max(now_sum1 - 1, 0)
                    else:                   
                        if val == -1:
                            for j in range(i, len(S)):
                                if S[j] == "0":
                                    if (j - i) % 2 == 0:
                                        val = 0
                                    else:
                                        val = 1
                                    break
                                elif S[j] == "1":
                                    if (j - i) % 2 == 0:
                                        val = 1
                                    else:
                                        val = 0
                                    break
                        if val == 1:
                            now_sum0 = max(now_sum0 - 1, 0)
                            now_sum1 += 1
                        elif val == 0:
                            now_sum0 += 1
                            now_sum1 = max(now_sum1 - 1, 0)
                        else:
                            return max(max_sum0, max_sum1)
                else:
                    return max(max_sum0, max_sum1)
        max_sum0 = max(max_sum0, now_sum0)
        max_sum1 = max(max_sum1, now_sum1)
    return max(max_sum0, max_sum1)

S = list(input())
print(min(solve(S), solve(S[::-1])))

Submission status: Wrong Answer

Solution code:
S=input()
l=len(S)
slist=list(S)
cnt=1
rlist=[]
i=1

while(i<l):
  if(slist[i-1]==slist[i]):
    cnt+=1
  else:
    rlist.append([slist[i-1],cnt])
    cnt=1
  i+=1

rlist.append([slist[l-1],1])

j=1
max=0
length=len(rlist)

while(j<length-1):
  a=rlist[j-1][0]
  b=rlist[j-1][1]
  c=rlist[j][0]
  d=rlist[j][1]
  e=rlist[j+1][0]
  f=rlist[j+1][1]
  if(c=="?" and a==e):
    tmpmax=b+f-d
    if(max<tmpmax):
      max=tmpmax
  j+=1

print(max)

Submission status: Wrong Answer

Solution code:
input = input()
min = 10000000000000000
nums =['']
for c in input:
    newnums = []
    if c == "0" or c == "1":
        for i in range(len(nums)):
            newnums.append(nums[i] + c)
    else:
        for i in range(len(nums)):
            newnums.append(nums[i] + "0")
            newnums.append(nums[i] + "1")
    nums = newnums
for num in nums:
    gap = 0
    max = 0
    min = 0
    for c in num:
        if c == "0":
            gap += 1
            max = gap if gap > max else max
        elif c == "1":
            gap -=1
            min = gap if gap < min else min
    x = max-min
    min = x if x < min else min
min = 0 - min if min < 0 else min 
print(min)

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)

def condition(n):
    l=-n
    r=n
    for i in range(N-1,-1,-1):
        l=max(-n,l)
        r=min(n,r)
        if l>r:
            return False
        if (1>r or l>1) and (-1>r or l>-1):
            return False
        if S[i]=="0":
            if (-1>r or l>-1):
                return False
            r+=1
            l+=1
        elif S[i]=="1":
            if (1>r or l>1):
                return False
            r-=1
            l-=1
        else:
            if (r>=1 and 1>=l) and (r>=-1 and -1>=l):
                r+=1
                l-=1
            elif (r>=1 and 1>=l):
                r-=1
                l-=1
            else:
                r+=1
                l+=1
                
    if r>=0 and 0>=l:
        return True

start=0
end=10**6
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)

Submission status: Wrong Answer

Solution code:
s=input()
result=0
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
if qus%2 ==1:
  result+= -1
max1=1
max2=0
last=""
news=""
zeroorone=0
for subs in s:
  if subs == "?":
    if last=="0" and zeroorone <=0:
      news+="1"
      last="1"
      zeroorone+=1
    elif last =="1" and zeroorone >=0:
      news+="0"
      last="0"
      zeroorone+=-1
    else:
      if len(news)>1:
        if news[-1]=="0" and zeroorone <=0:
          news+="1"
          last="1"
          zeroorone+=1
        elif zeroorone >=0:
          last="0"
          news +="0"
          zeroorone+=-1
        else:
          last="1"
          news +="1"
          zeroorone+=1          
      else:
        news += "0"
        last="0"
        zeroorone+=-1
    max1=1
    #last=subs
    continue
  news += subs
  if last == subs:
    max1+=1
  else:
    max1=1
    last=subs
  max2=max(max1,max2)  
result=max(result,max2)
zeros=news.count("0")
ones=news.count("1")
max2=abs(zeros-ones)
result=max(result,max2)
print(news)
max1=1
last=""
max2=0
for subs in news:
  if last == subs:
    max1+=1
  else:
    max1=1
    last=subs
  max2=max(max1,max2)  
result=max(result,max2)
print(result)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 二分探索、左右からの貪欲法、?をスキップした状態で1の連続数と0の連続数
S = list(sr())
answer = 0

def solve(S, bl):
    global answer
    one_seq = 0
    one_max = 0
    zero_seq = 0
    zero_max = 0
    cur = 0
    for i, s in enumerate(S):
        if s == '1':
            one_seq += 1
            zero_seq -= 1
            zero_seq = max(0, zero_seq)
            cur += 1
        elif s == '0':
            zero_seq += 1
            one_seq -= 1
            one_seq = max(0, one_seq)
            cur -= 1
        elif s == '?':
            if bl:
                if one_seq == answer:
                    S[i] = '0'
                    zero_seq += 1
                    one_seq -= 1
                    one_seq = max(0, one_seq)                    
                elif zero_seq == answer:
                    S[i] = '1'
                    one_seq += 1
                    zero_seq -= 1
                    zero_seq = max(0, zero_seq)
                else:
                    one_seq -= 1
                    zero_seq -= 1
                    one_seq = max(0, one_seq)
                    zero_seq = max(0, zero_seq)  # ここでは保留                    
            else:
                one_seq -= 1
                zero_seq -= 1
                one_seq = max(0, one_seq)
                zero_seq = max(0, zero_seq)  # ここでは保留
        if one_seq > one_max:
            one_max = one_seq
        if zero_seq > zero_max:
            zero_max = zero_seq
    answer = max(zero_max, one_max)
    return S    

S = solve(S, False)
S = solve(S, True)
S = solve(S[::-1], True)
S = solve(S, True)
S = solve(S[::-1], True)

print(answer)

Submission status: Wrong Answer

Solution code:
def examA():
    T = I()
    ans = [0]*T
    for t in range(T):
        N = I()
        A = LI()
        S = SI()
        if S[-1]=="1":
            ans[t] = 1
            continue


    print(ans)
    return

def examB():
    S = SI()
    N = len(S)
    sub_ = defaultdict(int)
    cur = 0
    keep = 0
    for i,s in enumerate(S):
        if s=="?":
            if cur==0:
                keep = i
            cur += 1
        else:
            if cur>0:
                sub_[keep] = cur%2
                sub_[i-1] = cur % 2
            cur = 0
    flag = True
    for i,s in enumerate(S):
        if i%2==0:
            if s=="1":
                flag = False
                break
        else:
            if s=="0":
                flag = False
                break
    if flag:
        print(1)
        return
    flag = True
    for i,s in enumerate(S):
        if i%2==1:
            if s=="1":
                flag = False
                break
        else:
            if s=="0":
                flag = False
                break
    if flag:
        print(1)
        return
    ans = 2
    cur = 0
    cur0 = [0]*N
    for i,s in enumerate(S):
        if s=="0":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
        cur0[i] = cur
    cur = 0
    cur1 = [0]*N
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
        cur1[i] = cur
    cur = 0
    for i,s in enumerate(S[:-1]):
        if s=="0":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
    cur = 0
    for i,s in enumerate(S[::-1]):
        if s=="1":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur

    max0 = set()
    for i,s in enumerate(S[1:],1):
        if s == "?" and cur0[i-1] == ans:
            max0.add(i)

    max1 = set()
    for i,s in enumerate(S[1:],1):
        if s == "?" and cur1[i-1] == ans:
            max1.add(i)
    #print(cur0)
    #print(cur1)
    #print(max1)

    cur = 0
    ne = 0
    for i,s in enumerate(S):
        #print(cur)
        if s=="0":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max1:
                #print(i,s,sub_)
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    ne = 0
    cur = 0
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max0:
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return

    cur = 0
    ne = 0
    for i,s in enumerate(S[::-1]):
        #print(cur)
        if s=="0":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max1:
                #print(i,s,sub_)
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    ne = 0
    cur = 0
    for i,s in enumerate(S[::-1]):
        if s=="1":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max0:
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    print(ans)
    return

def examC():
    N, A, B = LI()

    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn

111??000
111?000
11??11
11???00
"""

Submission status: Wrong Answer

Solution code:
s = input()
a = len(s)
if (s[0]=="0"):
    d = [(-1,0)]
elif (s[0]=="1"):
    d = [(1,0)]
else:
    d = [(0,1)]   #(差、？の数)
for i in range(1,a):
    p,q = d[-1][0],d[-1][1]
    if (s[i]=="0"):
        d.append((p-1,q))
    elif (s[i]=="1"):
        d.append((p+1,q))
    else:
        d.append((p,q+1))
#print(d)
now = [0]
res = []
for i in range(a):
    if (s[i]=="?"):
        if (d[i][0]+now[-1]<=0):
            now.append(now[-1]+1)
            res.append(1)
        else:
            now.append(now[-1]-1)
            res.append(0)
            
    else:
        now.append(now[-1])
#print(now)
mi = 0
ma = 0
l = []
for i in range(a):
    x = d[i][0]+now[i+1]
    l.append(x)
    mi = min(mi,x)
    ma = max(ma,x)
#print(res)
#print(l)
ans1 = ma-mi
#print(ans1)


now = [0]
res = []
for i in range(a):
    if (s[i]=="?"):
        if (d[i][0]+now[-1]<0):
            now.append(now[-1]+1)
            res.append(1)
        else:
            now.append(now[-1]-1)
            res.append(0)
            
    else:
        now.append(now[-1])
#print(now)
mi = 0
ma = 0
l = []
for i in range(a):
    x = d[i][0]+now[i+1]
    l.append(x)
    mi = min(mi,x)
    ma = max(ma,x)
#print(res)
#print(l)
ans2 = ma-mi
print(min(ans1,ans2))