Arrange strings for maximum overlap

Question

Let's say I have this set of strings:

strings = {'qqq', 'eqq', 'qqw', 'www', 'qww', 'wwe', 'eee', 'eeq', 'wee', 'qwe'}

How do I write an algorithm that arranges the strings such that they overlap maximally? I already know that one way of arranging them is as follows:

qww
 www
  wwe
   wee
    eee
     eeq
      eqq
       qqq
        qqw
         qwe

However, I found the above result with a brute-force solution. Is there a cleverer way of doing this?

Answer 1

This is called the shortest superstring problem and is NP complete.

You might be interested in the approaches in the paper Approximation Algorithms for the Shortest Common Superstring Problem by Jonathan Turner.