build shortest string from a collection of its subsequence

Question

Given a collection of sub-sequences from a string.

For example:

abc
acd
bcd

The problem is, how to determine the shortest string from these sequences?

For the above example, the shortest string is abcd.

Here sub-sequences means part of a string but not necessarily consecutive. like acd is a sub-sequence of string abcd.

Edit: This problem actually comes from Project Euler problem 79, in that problem, we have 50 subsequences, each has the length of 3. and all characters are digits.

Answer 1

This problem is well studied and coined "Shortest common supersequence"

For two strings, it is in O(n). Suppose n is the maximum length of string. O(n) is used to build the suffix array and then O(n) to solve the Longest Common Subsequence problem.

For more than two strings, it is NP-Complete.