Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the length of the string.
For example starting with $S=abc$ this operation can get you all the permutations of $a, b, c$ except $cba$ (which you can get in two operations $abc\to bca\to cba$).
- Given two strings $S$ and $T$ can you decide in quadratic time if you can get $T$ by applying this operation once to $S$?
- Given two strings $S$ and $T$ can you decide in polynomial time if you can get $T$ by applying this operation to $S$ and then applying it once more to the result?
For both problems the alphabet is held constant.
There is a algorithm in cubic time for the first one (for each suffix of $T$ that is also a subsequence of $S$ check if $S$ is an interleaving of that suffix and the corresponding prefix).