# longest list of words with matching start and end letters

My friend gave me a problem that he says is easy, but I can't figure out a good algorithm to use to do it.

You are given an input of 100 random English words. You have to find the longest string of words where the last letter in one word matches the first letter in the next word. You can only use each word once.

For example, if you were given the words "cat", "dog", "that", the longest string you could make would be "cat -> that". If you were given the words "mouse", "moose", "unicorn", the longest string you could make would just be one word (since none of those words link). If you were given the words "bird", "dish", "harb", the longest string you could make would be "harb -> bird -> dish" (or "dish -> harb -> bird" or "bird -> dish -> harb").

I came up with the idea of modeling this as a directed cyclic graph. Each node would just be a word, with vertices going to each word/node that started with the letter this word ended with.

``````+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
|                  |
\|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \
``````

This problem appears to be a longest path search, which is NP-Hard.

Is there a better way to do it? Or even some sort of approximation algorithm that could be used? Or some way to exploit qualities of English to reduce the search space?

• With 100 words, you get (at least) 100! = 9.332622e+157 combinations. Good luck with that, I think your friend is pulling your leg saying this is easy. Aug 11, 2013 at 8:34
• But, the number of possible combinations is much less than that, because on average a single word is only linked to about 6 or 7 other words. Aug 11, 2013 at 12:56
• You are correct that this is exactly a longest path search. I think your friend is wrong. However, an exhaustive search is not hard to code, and may not run all that long. Aug 12, 2013 at 4:16
• Just for fun, I coded up a brute force exhaustive search (as @kevincline pointed out) in Ruby (gist.github.com/anonymous/6225361). With 100 words, it only took ~96 seconds (gist.github.com/anonymous/6225364 ). And this was a highly inefficient, un-optimized, interpreted-language, quick-and-dirty script. So with only 100 words even a slow version of brute force runs in a sane amount of time. My code doesn't actually create an acyclic graph and then search through it, it just recursively builds every possible path starting from each word, and keeps track of the longest ones. Aug 13, 2013 at 20:37
• The problem states that there are 100 words. I think this means you can apply a dynamic programming solution, which is mentioned in the article you are referring to. Aug 14, 2013 at 8:17

I think this is related to the longest path (LP) problem that you mentioned, but it's a little different. The primary difference is that the LP problem has a higher degree of connectivity than what your suggested problem does. By restricting your connections to the last and first letters, you remove a large number of potential combinations.

Here's how I would recommend tackling this one:

1. For each word in the list, count the possible connections in and connections out.
2. Discard any words that have 0 ins and 0 outs.
3. Identify an initial set of "starter words" with the lowest numbers of ins and outs, and the outs must be greater than 0.
4. Each starter word receives its own working copy of the ins / outs connection count. This forms the head of the chain.
5. For each chain, identify a list of "next words" based upon:
• last letter of starter or previous word
• lowest number of of ins and outs connections (again, the outs must be greater than 0)
6. For each `next word`, repeat step 5 until the chain terminates.

Keep in mind that:

• You'll need to keep track of the length of the chains and have some global mechanism to identify the longest chain.

• You'll also need to remove each word from the working copy of the connection counts in order to avoid a recursive loop.

• At some point, your chain will terminate and you have to select a word with a 0 connection out count.

• You may have to recalculate ins / outs as words are removed from the working lists. At first glance, I don't think this will be necessary as the overall sets will be relatively small. If you scaled out to 1000 words, then having static counts may slow down the algorithm from converging.

I kind of saw this as a packing problem. To me, the connections in and out identify the shape to be packed. The lower the connections, the more odd the shape. The more odd the shape, the sooner I want to pack it as I perceived having decreasing odds of being able to pack an odd shape the later I got into the chain.

As an example:

``````{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this
``````
• Is there any guarantee that this algorithm will always find the longest path? Off the top of my head, I can't think of a counter-example, but this seems like it might fall for a "local maximum" type solution. Aug 14, 2013 at 19:48
• @BenLee - I'm a software engineer; I never guarantee my code. :-) Seriously though, I don't know the answer to your question. My set theory and mathematical proof skills are weak, to put it mildly, so I don't have any way beyond empirical evaluation to validate my algorithm. I'm not sure this problem is really NP-hard, but I can't validate that claim either. If it's not NP-hard then there ought to be a means to validate the algorithm.
– user53019
Aug 14, 2013 at 20:46
• What about a word list like this: "dog, gopher, bun, nun, noon, nub". The algorithm would incorrectly pick the longest list as "dog -> gopher", when it actually is any combination of "bun, nun, noon, nub". Aug 15, 2013 at 9:19
• @AbeTool - good example there. I would add another iteration (or two) to allow for "lowest input >= 1" and "lowest output >= 1" combinations then.
– user53019
Aug 15, 2013 at 11:50
• I don't think that's going to solve the problem in all cases. I think this falls into a "local maximum" type solution. Aug 17, 2013 at 3:33

If you make 26X26 matrix to represent directed graph of vertex as each alphabet and words as edge. For example word - APPLE connect vertex A and E with edge directed from A to E. Now the problem reduces to finding largest Eulerian trail (path which includes maximum number of edges, visiting each edge once wit possible repetition of vertices) in the graph. One of the O(E) algorithm would be to start randomly from a pair of vertices. Find a path between them. Than keep relaxing the path till it is possible.

update @GlenH7 I solved a similar question on www.hackerearth/jda recently, there was relative marks with respect to best solution and I scored the highest marks with the following approch-

Given list of words. Find the longest chain that can be formed by them. A chain is valid if every word begin with a letter *ending at the ending of last word.

Approch =

1)make the graph of alphabets as vertices and words as edges. In place of using multiple edges use one with weight equal to number of edges.

2)find the strongly connected component of graph with maximum edges. Temporarily discard other edges.

3)For each vertex make its indegree equal to its outdegree.

4)Now their exists eulerian circuit in graph. Find it.

5)Now in remaining graph(w.r.t orignal graph find the longest trail with first vertex in chosen strongly connected component. I think this is NP hard.

6)Include the above trail in Elerian circuit converting eulerian circuit into trail.

Why - I accept that this question is most probably NP hard(guess, not mathematically speaking). But the above approach works best when there is a long list(1000+) of uniformly distributed words(i.e. not intended to be w.c. for above approach). Let us assume that after converting given list to graph mentioned above, it luckily turns out to be a eulerian graph(see http://en.wikipedia.org/wiki/Eulerian_path for conditions), then without any doubt we can say that answer to above question is P and is actually the eulerian path in the graph(see http://www.graph-magics.com/articles/euler.php for a very simple approch to do so and see this to verify that your graph has single http://www.geeksforgeeks.org/strongly-connected-components/ and if not temporarily clean other small scc because eulerian path exists for single scc). Thus for not lucky cases(which are almost all cases) I try to convert them to lucky cases(i.e eulerian trail condition are fulfilled). How to do this? I tried do increasing depth search for irrelevant edges(the set of edges in a path staring from vertex with outdegree greater than indegree and ending at vertex with indegree greater than outdegree). Increasing depth search means that first I searched for all such set of one edge in path than two edges in path and so on. It may seem at first look that ith depth search would take O(nodes^i) thus total time complexity of O(nodes + nodes^2 + nodes^3 + ....) till it is a lucky case. But amortized analysis will revel it is O(edges). Once it is reduced lucky case find eulerian circuit.

Till here it was all polynomial time. This would give almost the best solution. But to further increase your solution(perfect solution is NP hard) try some greedy approach in remaining graph to find a long trail staring with one of vertices in chosen scc. Now add this to above found eulerian trail to further increase it.

• @GlenH7 I solved a similar question on www.hackerearth/jda recently, there was relative marks with respect to best solution and I scored the highest marks with the following approch- Jul 3, 2014 at 16:38

Idea:

First, create two maps (hashes), say, S, and E, from alphabet letters to words; the first, S, maps starting letters to words, the second, E, does the same with ending letters.

E.g., if the dictionary is made of:

bird, dish, dog, harb

we have:

``````S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...
``````

and,

``````E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...
``````

Next, using S and E for fast lookups, create a forest (set of trees), of the same size as the dictionary, with roots at each word, and not allowing a word to appear more than once in a tree -- cache the trees' depths as you construct them:

``````bird (depth: 2)
dish
harb
dog

dish (depth: 3)
harb
bird
dog

dog (depth: 0)

harb (depth: 2)
bird
dish
dog
``````

Finally, iterate over the forest and find the tree(s) of greatest depth.

The solution(s) will be on the descendant axis of those trees.

E.g.,

``````dish / harb / bird / dog
``````

above.