能操作的串太多不好考虑，尝试找到一些基础操作，使得任意一个组合都能由基础操作拼成，再对基础操作考虑就可能会轻松一些。
首先 \(00\to 0, 11\to 0\) 这两个操作肯定属于基础操作，尝试往更长的串讨论：
- \(s1111\operatorname{rev}(s)\to 0\)，可以看作 \(s\ 11\ 11\ \operatorname{rev}(s)\to s00\operatorname{rev}(s)\) 再操作下去。
- \(s0110\operatorname{rev}(s)\to 0\)，可以看作 \(s0\ 11\ 0\operatorname{rev}(s) \to s\ 00\ 0\operatorname{rev}(s) = s00\operatorname{rev}(s)\) 再操作下去。
- \(s0000\operatorname{rev}(s)\to 0\)，和 \(1111\) 的情况一致。
- \(1001\to 0\)，无法由已知的基础操作得到，所以也加入基础操作，继续讨论：
- \(s 110011 \operatorname{rev}(s)\to 0\)，可以看作 \(s\ 11\ 00\ 11 \operatorname{rev}(s)\to s 0000 \operatorname{rev}(s)\) 然后继续操作。
- \(s 010010 \operatorname{rev}(s)\to 0\)，可以看作 \(s0\ 1001\ 0\operatorname{rev}(s)\to s000\operatorname{rev}(s)\) 然后继续操作。
所以基础操作只有 \(00\to 0, 11\to 0, 1001\to 0\) 这三种。
因为 \(00\to 0, 11\to 0\) 的存在，最后的答案一定是 \(01\) 交错的形式，因为 \(00\to 0\) 的存在，一个 \(\ge 2\) 的 \(0\) 连续段都可以被消为单个 \(0\)，主要还是考虑保留下尽可能少的 \(1\)。
考虑到 \(11\to 0, 1001\to 0\)，这说明两个 \(1\) 之间有 \(0\) 或 \(2\) 个 \(0\) 都是可以消除的，且同时因为 \(00\to 0\) 的存在，\(\ge 3\) 个 \(0\) 可以被消到 \(2\) 个 \(0\)，所以两个 \(1\) 之间只要不是 \(1\) 个 \(0\) 都可以消。
于是考虑把 \(1\) 分段，每个段内相邻的 \(1\) 之间都是恰好 \(1\) 个 \(0\)。 一个段内部的 \(1\) 不能在内部消除，只能相邻两个段挨着的头尾的 \(1\) 可以消除。且如果一个段没有 \(1\) 了显然就不重要了可以删掉这个段（这里其实有一点小问题，下面的证明会说）。
于是记 \(a_{i}\) 表示第 \(i\) 段的 \(1\) 的数量，问题转为了：
- 可以选择 \(a_{i}, a_{i + 1}\) 各减 \(1\)，若为 \(0\) 则删去。问最后的 \(\sum a_{i}\) 最小值。
这是比较经典的，记 \(s, m\) 表示 \(a_{i}\) 的和与最大值，答案即为 \(\max(s\bmod 2, m - (s - m))\)，前面一个式子处理奇偶，后面一个式子处理最大值特别大的情况。
这也是可以构造的：
- 每次找到 \(a_{i} = m\) 的 \(i\)，选择相邻的 \(i - 1, i + 1\) 操作即可。操作完 \(s\gets s - 2, m\gets m - 1\)，\(s\) 奇偶性不变，\(m - (s - m)\) 也不变。（若存在 \(2\) 个 \(i\) 满足 \(a_{i} = m\)，则说明此时就是 \(2\) 个 \(m = \frac{s}{2}\)，合法）。
- 这里有一个小问题，\(1111\) 若选择中间的 \(11\) 操作变为 \(101\)，\(a\) 从 \([1, 1, 1, 1]\) 变为了 \([2]\)，此时合并了两边的段。但是分析一下，若选择的 \(a_{i}, a_{i + 1}\) 存在一个 \(> 1\)，则两个 \(1\) 消去变为的 \(0\) 附近一定还会有 \(1\) 个 \(0\)，\(0\) 的个数就一定 \(\ge 2\)，不会合并段。也就是说，只有 \(a_{i} = a_{i + 1} = 1\) 时可能出现这个这个问题，那么此时 \(a\) 这个序列是全 \(1\) 的，从一端逐步合并即可。
确定了剩下的 \(1\) 的个数 \(c\) 后，最后的答案就被限制在了 \([2c - 1, 2c + 1]\) 中，这取决于最左侧会不会有 \(0\) 和最右侧会不会有 \(0\)。 左侧没有 \(0\) 当且仅当原串第一个数为 \(1\) 且这个 \(1\) 始终没有被消，右侧同理，于是就可以分讨了：
- 若 \(m > s - m\)，则说明操作一定是把取到 \(a_{i} = m\) 的 \(i\) 这一段不断与左右相消。所以若原串第一个数为 \(1\) 且该 \(1\) 在最大段内时左侧不会有 \(0\)，右侧同理。
- 若 \(m\le s - m\)，则分讨一下 \(s\bmod 2\)：
- \(s\bmod 2 = 0\)，则答案为 \(1\)。
- \(s\bmod 2 = 1\)，考虑原串第一个数为 \(1\) 的话能否保证不被消。
回归 \(a\) 的判定，钦定第一个 \(1\) 不被消，就相当于 \(a_{1}\gets a_{1} - 1\)，此时 \(s' = s - 1, m - 1\le m'\le m\)，于是此时一定有 \(s'\bmod 2 = 0, m'\le s - m'\)，也就是一定可以消完。所以该 \(1\) 一定可以不被消，答案为 \(2\)。
右侧也是同理的，如果都不满足则答案为 \(3\)。
时间复杂度 \(\mathrm{O}(n)\)。