假设 $s_{n}$ 在答案 $t$ 中的最后一次出现位置是 $t_i$，那么 $t[1:i-1]$ 一定包含了 $s[1:n-1]$ 除本身以外的所有子序列，且不包含 $s[1:n-1]$ 作为子序列。并且如果 $s_{n-1}\ne s_n$，需要在 $t_i$ 之后还有一个 $s_{n-1}$ 才能保证 $s[1:n-1]$ 出现。这样就将问题递归到了 $s[1:n-1]$ 上，重复这个过程直到 $|s|=1$，那么答案就是空串。

根据这个递归过程反过来构造即可，时间复杂度 $O(n)$。注意到这个过程实际上证明了长度最短的 $t$ 是唯一的。