output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: # 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):
      global answer
      one_seq = 0
      one_max = 0
      one_start = set()
      zero_seq = 0
      zero_max = 0
      zero_start = set()
      cur = 0
      for i, s in enumerate(S):
          if s == "1":
              one_seq += 1
              zero_seq -= 0
              zero_seq = max(0, zero_seq)
              cur += 1
          elif s == "0":
              zero_seq += 1
              one_seq -= 0
              one_seq = max(0, one_seq)
              cur -= 1
          elif s == "?":
              one_seq -= 1
              zero_seq -= 1
              one_seq = max(0, one_seq)
              zero_seq = max(0, zero_seq)  # ここでは保留
          if one_seq > 0 and one_seq == one_max:
              one_start.add(i - one_seq + 1)
          elif one_seq > 0 and one_seq > one_max:
              one_start = {i - one_seq + 1}
              one_max = one_seq
          if zero_seq > 0 and zero_seq == zero_max:
              zero_start.add(i - zero_seq + 1)
          elif zero_seq > 0 and zero_seq > zero_max:
              zero_start = {i - zero_seq + 1}
              zero_max = zero_seq
      answer = max(one_max, zero_max)
      one_seq = 0
      zero_seq = 0
      cur = 0
      for i, s in enumerate(S):
          if s == "1":
              one_seq += 1
              zero_seq -= 0
              zero_seq = max(0, zero_seq)
              cur += 1
          elif s == "0":
              zero_seq += 1
              one_seq -= 0
              one_seq = max(0, one_seq)
              cur -= 1
          elif s == "?":
              if zero_seq == answer and i + 1 in one_start:
                  zero_max += 1
                  answer += 1
                  return None
              elif one_seq == answer and i + 1 in zero_start:
                  one_max += 1
                  answer += 1
                  return None
              if i + 1 in one_start:
                  S[i] = "0"
                  cur -= 1
              elif i + 1 in zero_start:
                  S[i] = "1"
                  cur += 1
              else:
                  one_seq -= 1
                  zero_seq -= 1
                  one_seq = max(0, one_seq)
                  zero_seq = max(0, zero_seq)  # ここでは保留
      return S
  
  
  for i in range(10):
      ret = solve(S)
      if ret:
          S = ret
      solve(S[::-1])
  
  
  print(answer)
  
problem_description: 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'.
samples: [{"input": "0??", "output": "1\n    \n\nWe can make S'= `010` and achieve the minimum possible unbalancedness of 1.\n\n* * *"}, {"input": "0??0", "output": "2\n    \n\n* * *"}, {"input": "??00????0??0????0?0??00??1???11?1?1???1?11?111???1", "output": "4"}]