文字を手前に追加できないので，\(s[0] = t[0]\) が必要なのは明らかです．さらに，\(t[0] = t[1] = \dots = t[k]\) であれば，この部分にも文字を挿入できないので \(s[0] = s[1] = \dots = s[k]\) が必要です．これらの条件が満たされているとき，\(s\) が \(t\) の（連続するとは限らない）部分列であることが Yes であるための必要十分条件となります．

必要性は明らか（部分列でなければ，無条件で文字を挿入できたとしても不可能）なので，十分性を確認しましょう．冒頭の同じ文字が連続する部分を除いた文字列を後ろから見て，貪欲に同じ文字同士を対応付けたとします．このとき，間の部分は必ず埋められます．すなわち，\(s[i] = t[k_1],~s[i + 1] = t[k_2]\) と対応付いていたとすると，\(t[k_1 + 1], t[k_1 + 2], \dots, t[k_2 - 1]\) を（適切な順序で）挿入できることを示します．

\(t[j]\) \((k_1 < j < k_2)\) が挿入できるかを考えます．\(t[j] \neq s[i]\) であるような文字は，後ろから順に挿入することにすれば，常に \(t[k_1] = s[i]\) の直後に挿入することになり，これは可能です．また，\(t[j] = s[i]\) である場合でも，\(t[j'] \neq t[j] = s[i]\) であるような \(k_1 < j' < j\) が存在すれば，上で \(t[j']\) を挿入した直後に \(t[j]\) を挿入することができます．したがって，挿入できない文字が存在するとすれば \(t[k_1 + 1] = s[i]\) が成り立ちますが，これは以下の通り矛盾を導くため起こり得ません．\(s[i]\) が冒頭部分に含まれているとすると，最初の仮定に矛盾します．（ \(s[i] = t[k_1]\) が冒頭部分であって \(t[k_1 + 1] = s[i] = t[k_1]\) であれば，\(s[i+1] = t[k_1 + 1]\) となってここまで冒頭部分に含まれているはずです．）また，冒頭部分以外は後ろから貪欲に同じ文字を対応付けたので，\(s[i] = t[k_1 + 1]\) と対応付けることが可能なのに \(s[i] = t[k_1]\) と対応付いているのは矛盾です．よって，十分性も示せました．

冒頭の処理と残りの貪欲な対応付けはそれぞれ \(\mathrm{O}(|s| + |t|)\) 時間ででき，この問題が解けました．