目標が達成されているとき，最終的な \(S\) の形は，(0 が \(0\) 個以上)(1 が \(0\) 個以上)(0 が \(0\) 個以上) という，\(3\) つの状態からなる形で必ず書き表されます．

したがって，次のような DP を考えることで解けます．

• \(\mathrm{dp}[i][j] = \) (\(S\) の \(i\) 文字目までを書き換えて目標を達成する際，最後の文字が \(j\) 番目の状態に属しているとしたとき，書き換える必要のある文字数の最小値)

遷移を考えます．今見ている文字が属している状態の文字と同じであれば書き換える必要はなく，逆に異なれば書き換える必要があることを考えると，

• \(\mathrm{dp}[i][0] \leftarrow \mathrm{min}(\mathrm{dp}[i][0], \mathrm{dp}[i - 1][0] + \mathrm{isdif}(S_i, 0))\)
• \(\mathrm{dp}[i][1] \leftarrow \mathrm{min}(\mathrm{dp}[i][1], \mathrm{dp}[i - 1][0] + \mathrm{isdif}(S_i, 1))\)
• \(\mathrm{dp}[i][1] \leftarrow \mathrm{min}(\mathrm{dp}[i][1], \mathrm{dp}[i - 1][1] + \mathrm{isdif}(S_i, 1))\)
• \(\mathrm{dp}[i][2] \leftarrow \mathrm{min}(\mathrm{dp}[i][2], \mathrm{dp}[i - 1][1] + \mathrm{isdif}(S_i, 0))\)
• \(\mathrm{dp}[i][2] \leftarrow \mathrm{min}(\mathrm{dp}[i][2], \mathrm{dp}[i - 1][2] + \mathrm{isdif}(S_i, 0))\)

と書けます．ただし，\(\mathrm{isdif}(c, x)\) は \(c\) が表す数が \(x\) と同じであれば \(0\)，異なれば \(1\) とします．計算量は \(O(N)\) です．