AT_agc045_b [AGC045B] 01 Unbalanced

给定一个字符串 $S$，其中每个字符都是 `0`、`1` 或 `?` 之一。 你可以将 $S$ 中的每个 `?` 替换为 `0` 或 `1`（每个 `?` 可以独立选择替换成哪一个），从而得到一个字符串 $S'$。现在定义 $S'$ 的“不平衡度”为： - $S'$ 的不平衡度 $= \max\{ |$从第 $l$ 个字符到第 $r$ 个字符之间 `0` 的个数与 `1` 的个数之差的绝对值$| : 1 \leq l \leq r \leq |S| \}$ 请你求出所有可能的 $S'$ 中，不平衡度的最小值。

输入为一行，包含一个字符串 $S$。

输出一个整数，表示所有可能的 $S'$ 的不平衡度的最小值。

## 限制 - $1 \leq |S| \leq 10^6$ - $S$ 的每个字符都是 `0`、`1` 或 `?` 之一。 ## 样例解释 1 如果令 $S' = $`010`，则不平衡度为 $1$，这是最小值。 由 ChatGPT 4.1 翻译