When \(N=2\), construction is possible only when \(t\) is \(s_1s_2, s_1s_1,\) or \(s_2s_2\).
Also, when \(s =t\), it is clearly possible to construct with zero operations.
Hereafter, we assume \(3 \le N, s \neq t\).

Next, we handle clearly impossible cases.
If a character contained in \(t\) does not exist in \(s\), it is clearly impossible to construct.
It is also impossible when \(t\) is like 0001, where only the last character differs from other characters. This can be shown from the fact that when performing the last operation, we need 1 at another position.

Otherwise, construction is always possible with at most \(N+1\) operations.
We will show this below.

Assume \(s_1 \neq s_N\). If \(s_1 =s_N\), we can satisfy this by performing one operation. Let \(x=s_1,y=s_N\).

From here, we consider performing \(N-2\) operations. In the \(i\)-th operation, we can append either 0 or 1 to the end by choosing one of the following:

• Append the first character to the end and delete the second character from the beginning
• Append the \((N-i+1)\)-th character from the beginning to the end and delete the \((N-i)\)-th character from the beginning

By performing operations appropriately, we can make \(s=xyt_2t_3\ldots,t_{N-1}\). For \(x\) and \(y\), we keep \(t_1\) and delete the one that is not \(t_1\). Without loss of generality, assume \(y\) is deleted.

At this point, if \(s=t\), construction is complete.
Otherwise, we choose the maximum \(i\) such that \(s_i =y\), append it to the end, and delete the \((i+1)\)-th character to achieve the goal.

Summarizing the above, construction is always possible with at most \(N+1\) operations.

Bonus:
Does there exist a case where at least \(N+1\) operations are necessary for construction? If so, give one such case.