\(A'_{i}=\begin{cases} 0 \; (A_i=A_{i+1}) \\ 1 \; (A_i\neq A_{i+1}) \end{cases}\)

として、\(B'\) についても同様に定義します。 操作は、\(A'\) に対して、

• \(0\) を \(101\) に変化させる。
• \(1\) を \(111\) に変化させる。

のいずれかを行うことです。 操作によって先頭の文字、末尾の文字、\(A'\) の \(0\) の個数はいずれも不変なので、これらが異なる場合、答えは No です。 これらが等しいとします。 \(A'\) を \(0\) で区切り、各区間に \(1\) が何個あるかを考えます。 このとき、操作は

• 隣り合う項に \(1\) を足す。
• \(1\) 以上の項に \(2\) を足す。

に対応します。 \(1\) つ目の操作を同じ組合せの項に \(3\) 回以上行うとき、\(2\) 回を \(2\) つ目の操作に代用することができます。 よって、同じ隣接 \(2\) 項に \(1\) つ目の操作を行う回数は高々 \(2\) 回としてよいです。 左から順に数列を見ていき、直前の隣接 \(2\) 項に対して \(1\) つ目の操作を行った回数をキーにして、その状態が可能かどうかを \(\text{dp}\) で計算できます。 計算量は \(O(|A|+|B|)\) です。