CareerCup

The question does not say "find the path". Check if it is possible to do it. Create one array of the first characters and another of the last characters in the string. If there are n-1 matches (one character in the first and one character in the last need not match), then we can do the same. Simple!

Build a graph of the strings where string A has an edge to string B iff the last letter of A is the first letter of B. Then run the hamiltonian path algorithm on said graph.

The graph is directed graph.

Does a polynomial time alogorithm exists for finding hamiltonian circuits?

I believe finding hamilton circuits in a graph is an NP complete problem.

Creating two arrays with the first char & the last char = O(n) (Both arrays can be built at the same time by loading the first & the last char of every string. Do this for every string. This is proportional to the number of strings & hence O(n)).

Comparing the two arrays if exactly n-1 matches are present is again O(n). We dont need 2 loops. We can compare both arrays in a single step index-by-index. Hence, this is O(n).

So, total complexity is O(n) + O(n) = O(n).

O(n) is defenitely better than O(n^2). But, I'm not sure about the time complexity of Hamiltonian circuits.

I still need to work out the Hamiltonian solution but rest of the solutions proposed above would fail on following test set:

"aa", "eb", "bc"

Isn't Hamilton Circuit a NP-Complete problem?