First, the operation does not change the string that results from sorting \(S\). Thus, if sorting \(S\) and \(T\) results in different strings, we clearly cannot make \(S\) and \(T\) equal.

On the other hand, if sorting \(S\) and \(T\) results in the same string, we can always make \(S\) and \(T\) equal. (The proof is given later.) Below, assume that sorting \(S\) and \(T\) results in the same string.

For integers \(k(0 \le k \le N)\), let us consider the condition for us to be able to make \(S\) and \(T\) equal in \(k\) operations. Here, the process of performing the operation \(k\) times can be seen as the following.

• Let \(X\) be the string formed from the \((k+1)\)-th through \(N\)-th characters of \(S\). Insert each of the \(1\)-st through \(k\)-th characters of \(S\) at any position of \(X\).

Thus, \(S\) and \(T\) can be made equal if and only if \(X\) is a subsequence of \(T\).

The proof that we can always make \(S\) and \(T\) equal comes from the fact that when \(k=N\), \(X\) is an empty string.

Thus, a binary search on \(k\) solves the problem in \(\mathrm{O}(N\log N)\) time. Alternatively, one can reverse \(S\) and \(T\) and solve it greedily in \(\mathrm{O}(N)\) time.