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).

  • 2
    $\begingroup$ What is the source of the problem? $\endgroup$
    – orlp
    Commented Jun 6, 2021 at 18:58
  • 1
    $\begingroup$ @orlp my imagination (but maybe somebody has come up with it before I cannot be sure) $\endgroup$
    – zol
    Commented Jun 6, 2021 at 19:01
  • $\begingroup$ Please ask only one question per post. If you have two questions, you can post them separately as two separate posts. This helps keep the site organized and makes it more likely you'll get answers to both questions. $\endgroup$
    – D.W.
    Commented Jun 6, 2021 at 19:59
  • 1
    $\begingroup$ If $S$ and $T$ are permutations of letters (so no letter occurs more than once), the first problem can be solved in linear time: Renumber all the letters so that they appear in increasing order in $T$; the answer is "yes" iff $S$ consists of an interleaving of 2 increasing sequences, in each of which the $i$-th letter is 1 more than the $(i-1)$-th. (But generalising this to arbitrary strings in the obvious way multiplies the running time by $k!$ for each letter that appears $k$ times.) $\endgroup$ Commented Jun 8, 2021 at 0:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.