← 返回题目列表

AtCoder · agc045_b

B. 01 不平衡

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是一个字符串 S,其中每个字符是 0, 1,或 ?.

考虑制作一个字符串 S' 通过替换每次出现的 ? 与 0 or 1 (我们可以为每个选择字符 ? 独立)。 让我们定义不平衡性 S' 如下:

  • (不平衡 S') = \max \{ 出现次数之间的绝对差 0 和 1 之间 l-th 和 r- 第一个字符 S (含) :\ 1 \leq l \leq r \leq |S|\}

找出最小可能的不平衡度 S'.

约束

  • 1 \leq |S| \leq 10^6
  • 每个字符 S is 0, 1,或 ?.

输入

输入由标准输入按以下格式给出:

S

输出

打印以下可能的最小不平衡度 S'.


示例输入 1

0??

示例输出 1

1

我们可以使 S'= 010 并实现最小可能的不平衡 1.


示例输入 2

0??0

示例输出 2

2

示例输入 3

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

示例输出 3

4