Construct back the original string

Question

I came across an interesting Strings problem, but couldn't solve it. Suppose we are given N strings each of 3 characters, we need to construct a string of length N+2 such that it contains all of the above N strings as substrings. If the solution doesn't exist- Print "-1" Can anyone help me out in solving this?

Answer 1

My answer is similar in nature to Pham Trung's one, but I choose to construct another graph for which the problem can be solved efficiently.

1. First, note that each of the given pieces has to appear in our result exactly once. There are N pieces and N places where they can appear. When all the given pieces are different, this must be a bijection (one-to-one correspondence). When some of them are the same, the statement is not clear, but one can suspect we still have to place each piece exactly the number of times it occurs in the input.

2. Now, construct the graph where each possible string of length 2 (one less than the size of a piece) is a vertex. For each piece αβγ in the input, construct an arc from vertex αβ to vertex βγ. Our task is now equivalent to finding an Eulerian path in this graph: a path of N arcs which traverses each given arc exactly once. This is a common problem with a simple polynomial solution: one depth-first search will do, see the above link for details.