Solution
Approach 1: Dynamic Programming
Intuition
We have to put the words into a row, where each word may overlap the previous word. This is because no word is contained in any word.
Also, it is sufficient to try to maximize the total overlap of the words.
Say we have put some words down in our row, ending with word A[i]
. Now say we put down word A[j]
as the next word, where word j
hasn't been put down yet. The overlap increases by overlap(A[i], A[j])
.
We can use dynamic programming to leverage this recursion. Let dp(mask, i)
be the total overlap after putting some words down (represented by a bitmask mask
), for which A[i]
was the last word put down. Then, the key recursion is dp(mask ^ (1<<j), j) = max(overlap(A[i], A[j]) + dp(mask, i))
, where the j
th bit is not set in mask, and i
ranges over all bits set in mask
.
Of course, this only tells us what the maximum overlap is for each set of words. We also need to remember each choice along the way (ie. the specific i
that made dp(mask ^ (1<<j), j)
achieve a minimum) so that we can reconstruct the answer.
Algorithm
Our algorithm has 3 main components:
 Precompute
overlap(A[i], A[j])
for all possiblei, j
.  Calculate
dp[mask][i]
, keeping track of the "parent
"i
for eachj
as described above.  Reconstruct the answer using
parent
information.
Please see the implementation for more details about each section.
Complexity Analysis

Time Complexity: , where is the number of words, and is the maximum length of each word.

Space Complexity: .
Analysis written by: @awice.