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

New contributor
zol is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 2
    $\begingroup$ What is the source of the problem? $\endgroup$ – orlp Jun 6 at 18:58
  • 1
    $\begingroup$ @orlp my imagination (but maybe somebody has come up with it before I cannot be sure) $\endgroup$ – zol Jun 6 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. Jun 6 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$ – j_random_hacker Jun 8 at 0:13

Your Answer

zol is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.