\(s\) の各文字が \(t\) のどの文字に対応するかを考えます。 明らかに、\(s[0]\) は \(t[0]\) に対応する必要があります。

\(s[i]\) が \(t[j]\) に、\(s[i +1]\) が \(t[k]\) に対応するとき、\(t[j + 1], \ldots, t[k - 1]\) は挿入によって作る必要があります。挿入で作れる必要十分条件は、\(t[j + 1] \neq t[j]\) (またはこの間が空)であることです。以下それを示します。

必要であること

\(t[j + 1]\) は最終的に、\(t[j]\) を選択した結果挿入された文字です。よって、\(t[j] \neq t[j + 1]\) である必要があります。

十分であること

まず、\(t[j + 1], \ldots, t[k - 1]\) のうち、\(t[j]\) と異なる文字を後ろから順番に挿入していきます。例えば \(t[j], \ldots, t[k - 1] = "abcaabab"\) ならば、\(b,b,c,b\) の順に \(t[j]\) の直後に挿入することで、\("abcbb"\) が作れます。残った \(t[j]\) と同じ文字(この例では \('a'\))を追加することで求める文字列が完成できます。

よって、

\(dp[i][j] = \) \(s\) から \(i\) 文字、\(t\) から \(j\) 文字使った状態にできるか？

という DP をすることで、この問題を解くことができます。

遷移としては、\(dp[i][j] = true\) かつ、\(s[i] =t[j]\) のときに、まず \(dp[i + 1][j + 1] = true\) とし、\(t[j + 1] \neq t[j]\) ならば \(j\) は任意位置まで伸ばせるとしてよいです。(この操作は各 \(i\) に対して一番手前のものにだけ行えば、計算量は全体で \(O\left(|s||t|\right)\) となります。)