# Minimal length of a string that contains two strings

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.

• This problem has been studied under the name shortest common supersequence.
– Raphael
Jun 16, 2015 at 11:33
• 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.
– D.W.
Jun 17, 2015 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.

• shouldn't that be shortest common supersequence? (like you suggest in your comment at the question) Jun 16, 2015 at 12:49
• 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...
– Yoar
Jun 16, 2015 at 12:53
• @HendrikJan Yes. The OP looks for SCS, the algorithm gets there via an LCS.
– Raphael
Jun 16, 2015 at 13:51
• @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.
– Raphael
Jun 16, 2015 at 13:52
• @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.
– Raphael
Jun 16, 2015 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.

• 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!
– Yoar
Jun 16, 2015 at 10:38
• And if I have $xx$, $yy$ at some place at a and b, what I need to do?
– Yoar
Jun 16, 2015 at 10:42
• 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.
– phs
Jun 16, 2015 at 12:12
• If you can explain little bit more it will be great!! Thank you!!
– Yoar
Jun 16, 2015 at 13:14
• Run my explanations on an example. Take $a=$ TROLL and $b=$ LOL. What do you get?
– phs
Jun 17, 2015 at 7:40