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.