公式解説と同じ方針ですが、別の解釈を与えます。

与えられた文字列 \(S\) に対して、長さ \(|S|+1\) の \(0, 1\) からなる数列 \(A\) を以下で与えます。

\[ \begin{cases} A_1 = S[1]\\ A_k = S[k-1] \text{ xor } S[k] \quad (2 \le k \le |S|)\\ A_{|S|+1} = S_{N} \end{cases} \]

このようにして作った数列は元の文字列と1対1に対応するため、文字列に対する操作をこの数列に対する操作とみなして差し支えありません。元の文字列の区間 \([l, r]\) に対する操作は、数列 \(A\) に対して \(A_l, A_{r+1}\) にそれぞれ \(1\) を \(\text{xor}\) する操作です。また、最終状態では \(k = 2, 3, ..., |S|\) に対して \(A_k\) が \(0\) である必要があります。

\(2 \le k \le |S|\) なる \(k\) について \(A_k = 0\) である場合、答えは \(|S|\) です。（文字列はすべて \(0\) もしくはすべて \(1\) であるため、全体に対して高々 \(1\) 回操作をすればよいです。）そうではない場合、\(A_k = 1\) となる \(k\) に対して、\(l = k\) となるような操作か \(r+1 = k\) となるような操作を必ず行う必要があります。したがって、答えの上界は \(\max (|S|+1-k, k-1)\) です。また、実際に \(\max (|S|+1-k, k-1) = |S|+1-k\) である場合は区間 \([k, |S|]\) に、 \(\max (|S|+1-k, k-1) = k-1\) である場合は区間 \([1, k-1]\) に操作を行うことで上界が達成可能です。

したがって、\(A_k = 1\) であるような全ての \(k\) に対する \(\max (|S|+1-k, k-1)\) の最小値を答えることで \(O(|S|)\) でこの問題を解くことができます。