I have came across a coding problem. I am unable to understand the problem. Can anyone help me out:
PROBLEM STATEMENT
Consider a new order of english alphabets ( a to z ), that we are not aware of. What we have though, dictionary of words, ordered according to the new order.
Our task is to give each alphabet a rank, ordered list of words. The rank of an alphabet is the minimum integer R that can be given to it, such that:
if alphabet Ai has rank Ri and alphabet Aj has Rj, then
- Rj > Ri if and only if Aj > Ai
- Rj < Ri if and only if Aj < Ai
Points to note:
- We only need to find the order of alphabets that are present in the words
- There might be some cases where a strict ordering of words cannot be inferred completely, given the limited information. In that case, give the least possible Rank to every alphabet
- It can be assumed that there will be no direct or indirect conflict in different inferences got from the input
Input:
- First line consists of integer ‘W’, the number of words. 1 <= W <= 100
- Second line onwards, there are ‘W’ lines, given ordered list of words. The words will be non-empty, and will be of length <= 20 characters. Also all the characters will be lowercase alphabets, a to z
Output:
The alphabets, in order of their Rank, for alphabets with the same rank, print them in the order as we know it today
Examples
Input: 2 ba ab
Output: b a
Explanation: ab comes after ba implies that b < a
Input: 3 abc aca ca
Ouput: ab c
Explanation: from the first 2 words, we know b < c, and from the last 2 words, we know a < c. We don’t have an ordering between a and b, so we give both of them the same rank, and print them in the order as we know today: ab
SAMPLE INPUT
6 aaabc aaade bacd cde cda cca
SAMPLE OUTPUT
e a b d c
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
