output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: def solve(s):
      n = len(s)
      # count 0
      # ? -> 1
      res_0 = 0
      cnt_00 = 0
      cnt_01 = 0
      # count 1
      # ? -> 0
      res_1 = 0
      cnt_10 = 0
      cnt_11 = 0
      for i in range(n):
          if s[i] == "0":
              cnt_00 += 1
              cnt_10 += 1
          elif s[i] == "1":
              cnt_01 += 1
              cnt_11 += 1
          else:
              cnt_01 += 1
              cnt_10 += 1
          res_0 = max(res_0, cnt_00 - cnt_01)
          res_1 = max(res_1, cnt_11 - cnt_10)
          if cnt_00 < cnt_01:
              cnt_00 = 0
              cnt_01 = 0
          if cnt_11 < cnt_10:
              cnt_10 = 0
              cnt_11 = 0
      # print(res_0, res_1)
      if max(res_0, res_1) > 1:
          if res_0 != res_1:
              return max(res_0, res_1)
          else:
              # check
              # count 0
              # ? -> 1
              cnt_00 = 0
              cnt_01 = 0
              left_0 = 0
              # count 1
              # ? -> 0
              cnt_10 = 0
              cnt_11 = 0
              left_1 = 0
              max_0_flg = [0] * n
              max_1_flg = [0] * n
              for i in range(n):
                  if s[i] == "0":
                      cnt_00 += 1
                      cnt_10 += 1
                  elif s[i] == "1":
                      cnt_01 += 1
                      cnt_11 += 1
                  else:
                      cnt_01 += 1
                      cnt_10 += 1
                  # print(cnt_00 - cnt_01, left_0, cnt_11 - cnt_10, left_1)
                  if cnt_00 - cnt_01 == res_0:
                      for j in range(left_0, i + 1):
                          max_0_flg[j] = 1
                      left_0 = i + 1
                  if cnt_11 - cnt_10 == res_1:
                      for j in range(left_1, i + 1):
                          max_1_flg[j] = 1
                      left_1 = i + 1
                  if cnt_00 < cnt_01:
                      cnt_00 = 0
                      cnt_01 = 0
                      left_0 = i + 1
                  if cnt_11 < cnt_10:
                      cnt_10 = 0
                      cnt_11 = 0
                      left_1 = i + 1
              # print(max_0_flg, max_1_flg)
              # check
              flag_0 = False
              flag_1 = False
              count_q = 0
              flag_tie = False
              for i in range(n):
                  if max_0_flg[i] == 1:
                      flag_0 = True
                      if flag_1 and count_q % 2 == 1:
                          flag_tie = True
                      flag_1 = False
                      count_q = 0
                  elif max_1_flg[i] == 1:
                      flag_1 = True
                      if flag_0 and count_q % 2 == 1:
                          flag_tie = True
                      flag_0 = False
                      count_q = 0
                  elif s[i] == "?":
                      count_q += 1
                  else:
                      flag_0 = False
                      flag_1 = False
                      count_q = 0
  
              # tie break
              if flag_tie:
                  return res_0 + 1
              else:
                  return res_0
  
      else:
          # 0 happens
          flag_01 = False
          flag_02 = False
          # 1 happens
          flag_11 = False
          flag_12 = False
          for i in range(n):
              if s[i] == "0":
                  if i % 2 == 0:
                      flag_02 = True
                  else:
                      flag_01 = True
              elif s[i] == "1":
                  if i % 2 == 0:
                      flag_12 = True
                  else:
                      flag_11 = True
          flag_one = True
          if flag_01 and flag_02:
              flag_one = False
          if flag_11 and flag_12:
              flag_one = False
          if flag_one:
              # 1 is possible
              return 1
          else:
              return 2
  
  
  def main():
      s = input()
      res = solve(s)
      print(res)
  
  
  def test():
      assert solve("0??") == 1
      assert solve("0??0") == 2
      assert solve("??00????0??0????0?0??00??1???11?1?1???1?11?111???1") == 4
      assert solve("11?00") == 3
  
  
  if __name__ == "__main__":
      test()
      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"}]