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.
@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.
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.