Loading...
Loading...
Loading...
A student found the word list of a made-up language from a college fest game. It uses lowercase English letters, but its alphabet has its own order. The words are sorted by that order, the same way a dictionary is sorted: compare the first letter where two words differ, and a shorter word comes before any longer word that starts with it.
Find an order of all the letters that appear in the words that makes the list sorted. Many orders may work. Print the one that comes first when the orders themselves are compared in normal a–z order. If no order makes the list sorted, print IMPOSSIBLE.
IMPOSSIBLE.Example 1
Input
5 wrt wrf er ett rftt
Output
wertf
The pairs of neighbours give t before f, w before e, r before t and e before r. The only order is wertf.
Example 2
Input
2 abc ab
Output
IMPOSSIBLE
ab starts abc, so it must come first in any order. The list is not sorted, whatever the order.
Try the problem first. Open one hint at a time.
Compare only neighbouring words. The first position where they differ gives one rule: the letter in the first word comes before the letter in the second.
If there is no different position and the first word is longer, the list can never be sorted.
The rules form a one-way graph on letters. Count for each letter how many rules point into it, and take letters with a count of 0.
To get the order that comes first, always take the smallest free letter, using a PriorityQueue. If some letters are never taken, the rules have a loop.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor