Merge Words by Head-Tail Chaining

Given a list of lowercase words, merge them into a single string by repeatedly chaining words.

Chaining Rules

• The last character of the current string must equal the first character of the next word.
• When chaining, do not duplicate the shared character. For example, if 'abc' is followed by 'ctr', the result is 'abctr', not 'abcctr'.
• Words may be reordered arbitrarily to form a valid chain.

Deliverables

• Return any valid merged string that uses all words exactly once.
• If no such chain exists, return the string 'IMPOSSIBLE'.

Example

• Input: ['abc','rgn','ctr']
• Output: 'abctrgn'
  • Explanation: 'abc' + 'ctr' (shared 'c') -> 'abctr'. Then 'abctr' + 'rgn' (shared 'r') -> 'abctrgn'.

Constraints

• 1 <= n <= 10^5 (number of words)
• 1 <= len(word) <= 50 (length of each word)

Performance Expectation

• The algorithm should run in near-linear time with respect to the total input size (sum of lengths of all words).

Discussion Points

• The problem can be modeled by representing words as edges in a directed multigraph with 26 nodes (one for each letter 'a' through 'z'). The task then involves finding an Eulerian path.
• Consider edge cases such as:
  • Multiple words that could connect the same two characters (e.g., two instances of 'ab').
  • Self-loops (e.g., a word like 'aa').
  • Disconnected components in the graph.