60

Alien dictionary

Difficulty: HARD
Contributed By
Nishant Chitkara
Avg. time to solve
46 min
Success Rate
50%

Problem Statement
Suggest Edit

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']
Note:
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.
Note:
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.
Sample Input 1 :
2
3
a aa aaa
3
a b c
Sample Output 1 :
true
true
Explanation for Sample Output 1 :
For the first test case, the words are 'a', 'aa', and 'aaa'. Since the only unique character here is 'a', so the array to be returned will just be ['a']. The 'true' that is being printed just signifies that the output returned by the function is valid.

For the second test case, the words are 'a', 'b', and 'c'. The unique characters here are 'a', 'b', and 'c' (in that order), so the array to be returned will be ['a', 'b', 'c']
Sample Input 2 :
2
3
caa aaa aab
2
aa aab
Sample Output 2 :
true
true
Reset Code
Full screen
copy-code
Console