We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this problem?

For example, if $a=1011$ and $b=0100$, the minimal string that include both: $c=101100$. As you can see string $c$ includes both $a$ and $b$ (with the characters of $a$ appearing in the same order in $c$, possibly with other characters interspersed, and the same for $b$).

I think it can be solved by a dynamic programming algorithm.

  • 2
    $\begingroup$ This problem has been studied under the name shortest common supersequence. $\endgroup$ – Raphael Jun 16 '15 at 11:33
  • $\begingroup$ What have you tried? Where did you get stuck? You think it can be solved by dynamic programming; well, what dynamic programming algorithms did you come up with? Did you come up with a recursive relation? We want to help you understand concepts, not solve exercise problems for you. $\endgroup$ – D.W. Jun 17 '15 at 6:16

Following the explanation on Wikipedia,

Note that the result of neither step is necessarily unique.

Writing actual (pseudo)code, correctness proof and runtime analysis are easy exercises.

  • 2
    $\begingroup$ shouldn't that be shortest common supersequence? (like you suggest in your comment at the question) $\endgroup$ – Hendrik Jan Jun 16 '15 at 12:49
  • $\begingroup$ Thank you, but: 1. Can you explain me this - "insert the characters which are not part of the LCS in-order and in appropriate positions." please? 2. There is clearer explanation for the LCS, because what wrote at Wikipedia is unclear... $\endgroup$ – Yoar Jun 16 '15 at 12:53
  • $\begingroup$ @HendrikJan Yes. The OP looks for SCS, the algorithm gets there via an LCS. $\endgroup$ – Raphael Jun 16 '15 at 13:51
  • $\begingroup$ @Yoar No, I won't. To be blunt, I think that the descriptions on Wikipedia are clear enough assuming you want to invest any time and thought yourself. I have no interest in helping you if all you want is code. $\endgroup$ – Raphael Jun 16 '15 at 13:52
  • 1
    $\begingroup$ @Yoar It's explained with an example in the SCS article on Wikipedia. Say you have $a_1 \dots a_n$ as one sequence and $a_{i_1} \dots a_{i_k}$ with $k \leq n$ the LCS, you'll have to add $a_1 \dots a_{i_1-1}$, $a_{i_1+1}\dots a_{i_2 - 1}$, and so on in order to get an SCS. Similarly for $b$. Since $a_{i_x} = b_{j_x}$ for all $x \in [1..k]$ you can shuffle the parts between the characters of the LCS -- which are unequal, otherwise it would not be an LCS -- however you want. $\endgroup$ – Raphael Jun 16 '15 at 15:02

Hint: assume $a$ starts with a 1st letter $x$, hence is some $xa'$. Similarly, assume $b$ is some $yb'$.

Now what is the shortest word that contains $a$ and $b$ when $x=y$ (when $a$ and $b$ start with the same char)? And what if $x\not=y$? Finally, what if $a$ is the empty word $\epsilon$? Or if $b$ is $\epsilon$?

Solving all these cases will lead you to a dynamic programming solution.

PS: what you call "a string $s$ that includes all characters of $a$" is formally called a supersequence. Write it $a\leq s$. In particular, the number of occurrences of the symbols in $a$ and their left-to-right order must be accounted for in $s$ but not necessarily at contiguous positions.

  • $\begingroup$ I still don't understand - I made few examples with the hind that you gave my but I still stuck... What with the 2nd letter (of $a$ and $b$)? What I do with it? Thank you! $\endgroup$ – Yoar Jun 16 '15 at 10:38
  • $\begingroup$ And if I have $xx$, $yy$ at some place at a and b, what I need to do? $\endgroup$ – Yoar Jun 16 '15 at 10:42
  • 1
    $\begingroup$ When you look at $a=xa'$ and $b=yb'$ with $x\not=y$ you may either go for $xs$ where $s$ is a supersequence of $a'$ and $b$ or for $yt$ where $t$ is a supersequence of $a$ of $b'$. Compute $s$ and $t$ and see which is shorter. $\endgroup$ – phs Jun 16 '15 at 12:12
  • $\begingroup$ If you can explain little bit more it will be great!! Thank you!! $\endgroup$ – Yoar Jun 16 '15 at 13:14
  • 1
    $\begingroup$ Run my explanations on an example. Take $a=$ TROLL and $b=$ LOL. What do you get? $\endgroup$ – phs Jun 17 '15 at 7:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.