Find the orginal string from a given set of substrings with each substring being 3 letters only

Below are the input:

Input1: N -> The number of sub-strings
Input2: The array of N substrings.

Constraint: 1<= N <= 1000000000

Example1:

Input1: 3
Input2:{ 42y, 2ya, ya6}

Output: 42ya6

Example2:
Input1: 2
Input2: { abb, bba}

Output: abba

Any optimal approach apart from brute-force ?