In the easy subproblem we have to produce a new string which is longer then all ten words together. Therefore we can just concatenate all ten words and append any two characters to the end.
In the hard subproblem it is obvious that in order to fit the words into a 39-letter string two of the words will have to overlap. As we are guaranteed that a solution exists, we know that each input has to contain two words that can overlap.
There are four possibilities how a pair of words can overlap: they can share 1, 2, 3, or 4 common letters. For each pair of words we will check these four possibilities, until we find a pair that fits together.
As soon as we find an overlapping pair of words, we will combine them together into a new word that has fewer than 8 characters. We can then append the remaining 8 words to get a valid solution of length at most 39. If we got a solution that is too short, we fix it by appending arbitrary characters.
Some common pitfalls in the hard subproblem:
“For each pair of different words” fails if all ten input words are the same
Trying only overlaps by a single letter sometimes does not work, for example for the input ABCD BCDE FZZZ GZZZ HZZZ IZZZ JZZZ KZZZ LZZZ MZZZ the only solution is to merge ABCD and BCDE into ABCDE.