まず、操作によって \(S\) をソートした文字列が変わることはありません。よって、\(S,T\) をそれぞれソートした文字列が異なる場合明らかに \(S,T\) を一致させることは出来ません。

逆に、\(S,T\) をそれぞれソートした文字列が一致するのであれば必ず \(S,T\) を一致させることが出来ます。(証明は後程述べます。)以降、\(S,T\) をそれぞれソートした文字列は同じものとします。

整数 \(k(0 \le k \le N)\) に対して、\(k\) 回操作を行うときに、\(S,T\) を一致させることができる条件を考えます。ここで、\(k\) 回の操作は以下のようにみなせます。

• \(S\) の \(k+1\) 文字目から \(N\) 文字目までからなる文字列を \(X\) とする。\(X\) に \(S\) の \(1\) 文字目から \(k\) 文字目をそれぞれ好きなところに挿入する。

よって、\(X\) が \(T\) の部分列となっていることが \(S,T\) を一致させるための必要十分条件です。

\(S,T\) を一致させることが出来る証明は、\(k=N\) のとき、\(X\) は空文字列であるためです。

よって、\(k\) を二分探索することで \(\mathrm{O}(N\log N)\) でこの問題を解くことが出来ます。\(S,T\) を逆から見て貪欲法を行うことによって \(\mathrm{O}(N)\) で解くこともできます。