There is an array of strings. Suppose there is a string whose last character matches with the first character of another string. In that case those two form a ring. You have the find the maximum length of the ring formed by the strings in the array. Let me explain the problem with an example. Suppose the array of strings is {ear, track, tired, rat, doe}. Here the maximum ring will be ear->rat->tired->doe>ear. So, the length will be 4.
If possible please provide code also .
Constraints?
in linear time.
I don't think it can be done in linear time, as essentially you are finding longest cycle in the graph, which has to be exponential according to me or maybe I am missing something.
What is the upper bound on the number of strings and the size of the alphabet? This cannot be done in linear time, but it may still be possible. This depends on the number of letters in the alphabet (i.e. is it only lowercase letters, or are uppercase letters allowed?) and on the maximum number of strings.
This is the approach for O(n*n) solution.
First of all, to work with graphs , we have to map strings with some integer(let by index in this problem).
Make the adjacency list as follows:
Now, by simply traversing in graph, find out the largest possible cycle.
Build a graph from the strings first. Then the size of the biggest strongly connected component is the answer. I haven't tried yet so I'm not sure whether it's correct or not.