Update appNew update is available. Click here to update.

Alien dictionary

Last Updated: 19 Jul, 2020
Difficulty: Hard


Try Problem

You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to you in the form of an array of strings called 'dictionary,' of size 'N.'

Example :
If the dictionary consists of the following words:-
["caa", "aaa", "aab"]
then, the order of alphabets are -
['c', 'a', 'b']
If the language consists of four letters, the four letters should be the starting four letters of the English language. However, their order might differ in the alien language.
Input format :
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the alien dictionary.

The second line contains 'N' single space-separated strings representing the words in the alien dictionary.
Output Format :
For each test case, return an array of characters representing the order in which they will appear in the alien language. The first element of the array shall represent the first letter of the alien language. The second one will represent the second letter of the language, so on and so forth. 

You do not need to print anything, just return the array of letters as they will appear in the language. 

Output for every test case will be printed in a separate line.
Note :
If your order is correct, the output will be true. Otherwise, it will be false.
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints :
1 <= t <= 100
0 <= N <= 10^5
0 <= Length of ARR[i] <= 10^5

Time Limit: 1 sec
Note :
The alien language consists of only lower case letters. However, their order might not be the same as the English language.