分数: 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