output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: import itertools
  import copy
  
  syokiti = list(input())
  
  last = []
  for i in itertools.product("10", repeat=syokiti.count("?")):
      yousuu = 0
      a = copy.deepcopy(syokiti)
      for kai, j in enumerate(a):
          if j == "?":
              a[kai] = i[yousuu]
              yousuu += 1
  
      ls = [j + 1 for j in range(len(a))]
      handan = []
      for j in itertools.combinations(ls, 2):
  
          j = list(j)
          renzoku = 0
          saisyo = a[0]
          saikouti = 0
          for k in range(j[0] - 1, j[1]):
              if a[k] == saisyo:
                  renzoku += 1
              else:
                  saisyo = a[k]
                  renzoku = 1
              if saikouti < renzoku:
                  saikouti = renzoku
  
          handan.append(saikouti)
      last.append(max(handan))
  
  print(min(last))
  
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"}]