output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: def main():
      S = input()
      size = [[[[0, 0]], []], [[], []]]
      length = 0
  
      for s in S:
          size2 = [[[], []], [[], []], [[], []]]
          if s != "0":
              for i in range(2):
                  for j in range(2):
                      if size[i][j]:
                          for x, y in size[i][j]:
                              if y == length + i:
                                  size2[i + 1][j ^ 1].append([y + 1, y + 1])
                                  if x != y:
                                      size2[i][j ^ 1].append([x + 1, y - 1])
                              else:
                                  size2[i][j ^ 1].append([x + 1, y + 1])
          if s != "1":
              for i in range(2):
                  for j in range(2):
                      if size[i][j]:
                          for x, y in size[i][j]:
                              if x == 0:
                                  size2[i + 1][j].append([0, 0])
                                  if x != y:
                                      size2[i][j ^ 1].append([x + 1, y - 1])
                              else:
                                  size2[i][j ^ 1].append([x - 1, y - 1])
          if len(size2[0][0] + size2[0][1]) == 0:
              size2 = size2[1:]
              length += 1
          else:
              size2.pop()
          for i in range(2):
              for j in range(2):
                  size2[i][j] = sorted(size2[i][j])
          size = [[[], []], [[], []]]
          for i in range(2):
              for j in range(2):
                  if len(size2[i][j]) == 0:
                      continue
                  size[i][j] = [size2[i][j][0]]
                  for x, y in size2[i][j][1:]:
                      size[i][j][-1][1] = max(y, size[i][j][-1][1])
  
      print(length)
  
  
  main()
  
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"}]