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:
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

    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()

n = len(S)
S = S+'2'
dp = [0]*(n+1)
last0 = 0
last1 = 0
for i in range(1, n+1):
  if S[i-1] == '0':
    last0 += 1
    a = abs(dp[i-1] + 1)
    b = last0
    if a >= b:
      dp[i] = dp[i-1] + 1
    else:
      dp[i] = b
    last1 = 0
  elif S[i-1] == '1':
    last1 += 1
    a = abs(dp[i-1] - 1)
    b = last1
    if a >= b:
      dp[i] = dp[i-1] - 1
    else:
      dp[i] = -b
    last0 = 0
  else:
    if dp[i-1] >= 0:
      last1 += 1
      a = abs(dp[i-1] - 1)
      b = last1
      if a >= b:
        dp[i] = dp[i-1] - 1
      else:
        dp[i] = -b
      last0 = 0
    elif dp[i-1] < 0:
      last0 += 1
      a = abs(dp[i-1] + 1)
      b = last0
      if a >= b:
        dp[i] = dp[i-1] + 1
      else:
        dp[i] = b
      last1 = 0
  if i>3 and dp[i-2]<0 and dp[i-1] == 2 and dp[i] == 1 and S[i] == '0':
    dp[i] = -1
  elif i>3 and dp[i-2]>0 and dp[i-1] == -2 and dp[i] == -1 and S[i] == '1':
    dp[i] = 1
print(max(map(abs, dp)))

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
            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

    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
    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:
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
            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

    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 = cur
            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 = cur
            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:
# ??00????0??0????0?0??00??1???11?1?1???1?11?111???1
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))



s = rr()
temp = s[0]
cnt = 0
li = []
for i in range(len(s) - 1):
    if s[i] == s[i+1] and temp == s[i]:
        cnt += 1
        continue
    else:
        li.append([temp, cnt+1])
        cnt = 0
        temp = s[i+1]
else:
    li.append([temp, cnt+1])
m = 1
if len(li) < 2:
    if li[0][0] != 63:
        m = li[0][1]
elif len(li) == 2:
    m = abs(li[0][1] - li[1][1])
else:
    for i in range(len(li) - 2):
        if li[i][0] == li[i+2][0] and li[i+1][0] == 63:
            if li[i+1][1] & 1:
                aaa = li[i][1] + li[i+2][1] - 1
                m = max(aaa, m)
            else:
                if li[i][1] == li[i+2][1]:
                    m = max(li[i+2][1]+1, m)
                else:
                    m = max(li[i+2][1], li[i][1], m)
        elif li[i][0] != 63:
            m = max(li[i][1], m)
print(m)

Submission status: Wrong Answer

Solution code:
S=input()
print(1)

Submission status: Wrong Answer

Solution code:
S = input()
a = S.count("0")
b = S.count("1")
print(abs(a-b))

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)
    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

    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)

    cur = 0
    for i,s in enumerate(S):
        if s=="0":
            cur += 1
        else:
            if s=="?" and i in max1:
                cur += 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            print(ans+1)
            return
    cur = 0
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
        else:
            if s=="?" and i in max0:
                cur += 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            print(ans+1)
            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
"""

Submission status: Wrong Answer

Solution code:
# ??00????0??0????0?0??00??1???11?1?1???1?11?111???1
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))



s = rr()
temp = s[0]
cnt = 0
li = []
for i in range(len(s) - 1):
    if s[i] == s[i+1] and temp == s[i]:
        cnt += 1
        continue
    else:
        li.append([temp, cnt+1])
        cnt = 0
        temp = s[i+1]
else:
    li.append([temp, cnt+1])
m = 1
for i in range(len(li) - 2):
    if li[i][0] == li[i+2][0] and li[i+1][0] == 63:
        if li[i+1][1] & 1:
            aaa = li[i][1] + li[i+2][1] - 1
            m = max(aaa, m)
        else:
            if li[i][1] == li[i+2][1]:
                m = max(li[i+2][1]+1, m)
            else:
                m = max(li[i+2][1], li[i][1], m)
    elif li[i][0] != 63:
        m = max(li[i][1], m)
print(m)

Submission status: Wrong Answer

Solution code:
# ??00????0??0????0?0??00??1???11?1?1???1?11?111???1
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))



s = rr()
temp = s[0]
cnt = 0
li = []
for i in range(len(s) - 1):
    if s[i] == s[i+1] and temp == s[i]:
        cnt += 1
        continue
    else:
        li.append([temp, cnt+1])
        cnt = 0
        temp = s[i+1]
else:
    li.append([temp, cnt+1])
print(li)
m = 1
for i in range(len(li) - 2):
    if li[i][0] == li[i+2][0] and li[i+1][0] == 63:
        if li[i+1][1] & 1:
            aaa = li[i][1] + li[i+2][1] - 1
            m = max(aaa, m)
        else:
            if li[i][1] == li[i+2][1]:
                m = max(li[i+2][1]+1, m)
            else:
                m = max(li[i+2][1], li[i][1], m)
    elif li[i][0] != 63:
        m = max(li[i][1], m)
print(m)

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)
    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

    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)

    cur = 0
    for i,s in enumerate(S):
        if s=="0":
            cur += 1
        else:
            if s=="?" and i in max1:
                cur += 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
    cur = 0
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
        else:
            if s=="?" and i in max0:
                cur += 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
    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
"""

Submission status: Wrong Answer

Solution code:
s=input()
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=""
for subs in s:
  if subs == "?":
    if last=="0":
      news+="1"
    elif last =="1":
      news+="0"
    else:
      if len(news)>1:
        if news[-1]=="0":
          news+="1"
        else:
          news +="0"
      else:
        news += "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:
# ??00????0??0????0?0??00??1???11?1?1???1?11?111???1
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))



s = rr()
temp = s[0]
cnt = 0
li = []
for i in range(len(s) - 1):
    if s[i] == s[i+1] and temp == s[i]:
        cnt += 1
        continue
    else:
        li.append([temp, cnt+1])
        cnt = 0
        temp = s[i+1]
m = 0
for i in range(len(li) - 2):
    if li[i][0] == li[i+2][0] and li[i+1][0] == 63:
        if li[i+1][1] & 1:
            aaa = li[i][1] + li[i+2][1] - 1
            m = max(aaa, m)
        else:
            if li[i][1] == li[i+2][1]:
                m = max(li[i+2][1]+1, m)
            else:
                m = max(li[i+2][1], li[i][1], m)
    elif li[i][0] != 63:
        m = max(li[i][1], m)
print(m)

Submission status: Wrong Answer

Solution code:
s=input()
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=""
for subs in s:
  if subs == "?":
    if last=="0":
      news+="1"
    elif last =="1":
      news+="0"
    else:
      if len(news)>1:
        if news[-1]=="0":
          news+="1"
        else:
          news +="0"
      else:
        news += "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:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()
n=len(s)
if n==1:
    print(1)
    exit()
x=[0]*n
y=[0]*n
a=0
b=0
mina=0
maxa=0
ra=0
minb=0
maxb=0
rb=0

for i in range(n):
    if s[i]=="0":
        a-=1
        b-=1
    elif s[i]=="1":
        a+=1
        b+=1
    else:
        a-=1
        b+=1
    x[i],y[i]=a,b
    if a>maxa:
        maxa=a
    if a<mina:
        mina=a
        maxa=a
    ra=max(ra,maxa-mina)
    if b>maxb:
        maxb=b
        minb=b
    if b<minb:
        minb=b
    rb=min(rb,maxb-minb)

c=0
ans=1
for i in range(n):
    if s[i]=="?":
        c+=1
    elif c>0 and i-c-1>=0:
        if c%2==1 and s[i-c-1]!=s[i]:
            ans=2
        if c%2==0 and s[i-c-1]==s[i]:
            ans=2
print(max(ra,abs(rb),ans))