题目描述

给定一个字符串 $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

输入

0??

输出

1

样例 2

输入

0??0

输出

2

样例 3

输入

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

输出

4

说明/提示

限制

• $1 \leq |S| \leq 10^6$
• $S$ 的每个字符都是 0、1 或 ? 之一。

样例解释 1

如果令 $S' =$010，则不平衡度为 $1$，这是最小值。

由 ChatGPT 4.1 翻译