{"problem":{"name":"01 Unbalanced","description":{"content":"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 `?` independent","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc045_b"},"statements":[{"statement_type":"Markdown","content":"Given is a string $S$, where each character is `0`, `1`, or `?`.\nConsider 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:\n\n*   (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|}$\n\nFind the minimum possible unbalancedness of $S'$.\n\n## Constraints\n\n*   $1 \\leq |S| \\leq 10^6$\n*   Each character of $S$ is `0`, `1`, or `?`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc045_b","tags":[],"sample_group":[["0??","1\n\nWe can make $S'=$ `010` and achieve the minimum possible unbalancedness of $1$."],["0??0","2"],["??00????0??0????0?0??00??1???11?1?1???1?11?111???1","4"]],"created_at":"2026-03-03 11:01:13"}}