\(N=2\) のとき、\(t\) が \(s_1s_2, s_1s_1,s_2s_2\) の場合のみ構成可能です。
また、\(s =t\) のとき、\(0\) 回の操作で明らかに構成可能です。
以降 \(3 \le N, s \neq t\) を仮定します。

次に明らかに構成不可能なケースを処理します。
\(t\) に含まれる文字が \(s\) に存在しない場合、明らかに構成不能です。
\(t\) が 0001 のような末尾の文字のみ他の文字と異なる場合も構成不可能です。 これは最後の操作を行うときに他の位置に 1 が必要なことから示せます。

それ以外の場合、必ず \(N+1\) 回以下の操作で構成可能です。
以降はそれを示します。

\(s_1 \neq s_N\) とします。\(s_1 =s_N\) の場合、\(1\) 回操作を行うことでこれを満たすことができます。\(x=s_1,y=s_N\) とします。

ここから \(N-2\) 回操作を行うことを考えます。 \(i\) 回目の操作では以下のどちらかを選んで行うことで 0 と 1 の好きな方の文字を末尾に追加できます。

• 先頭の文字を末尾に追加し、先頭から \(2\) 番目の文字を削除する
• 先頭から \(N-i+1\) 番目の文字を末尾に追加し、先頭から \(N-i\) 番目の文字を削除する

適切に操作を行うことで \(s=xyt_2t_3\ldots,t_{N-1}\) とすることができます。 \(x,y\) について \(t_1\) を残し、\(t_1\) でない方を削除を行います。 \(y\) が削除されたとしても一般性を失いません。

この時点で \(s=t\) なら構成が完了しています。
そうでない場合、\(s_i =y\) なる最大の \(i\) を選んで末尾に追加し、\(i+1\) 番目の文字を削除することで目的を達成できます。

上記をまとめると \(N+1\) 回以下の操作で必ず構成可能です。

おまけ：
構成には \(N+1\) 回の操作が最低限必要な場合は存在するでしょうか？存在する場合、具体例を \(1\) つ示してください。