Given multiple school children and the paths they took from their school to their homes, find the longest most common path (paths are given in order of steps a child takes).

Example:

child1 : a -> g -> c -> b -> e
child2 : f -> g -> c -> b -> u
child3 : h -> g -> c -> b -> x

result = g -> c -> b

Note: There could be multiple children. Input was not given as a string format, I did so in the examples to clarify the paths taken. The input was in the form of steps and childID and it was not ordered so you also had to put it in a map. For example input looked like this:

(child1, a)
(child2, f)
(child1, g)
(child3, h)
(child1, c)
...

As you can see, for child1 path is a -> g -> c, but the children themselves are not ordered, their steps are.

Damn guys, I never thought Amazon would ask such a difficult question, I suggested using a trie but afterwards I realized that I did not ask for another case where say a fourth child has the path g -> c -> b -> h -> x, in this case g -> c -> b is still the most common path but a trie will miss it (but I'm not sure though, maybe it would not be).

How do you solve this LC Jedi's?