IITKESO207SPA4A - Lexicographic Permutations

no tags 

Problem description

 

Given a list of N names, find a permutation of characters of the alphabet such that these N names are in lexicographic order with respect to that permutation. If no such permutation exists, print "IMPOSSIBLE".

 

Lexicographical order is defined in the following way : when we compare two strings s and t, first we find teh leftmost position with differeing characters. If there is no such poisition, the shortest string is lexicographically lower. Otherwise, we compare characters according to their order in the alphabet.

 

Input format

An integer N for the number of names, followed by n lines each containing a string of names all in small characters.

 

Output format

Print the permutation of the characters such that these names are in lexicographic order. If multiple such permutations are possible, then output the one that is lexicographically lowest.

 

Constraints :

 N will be in the set [1,1000] and each name will have length in the set [1,100]

 

Sample input

7

motwani
hopcroft
ullman
cormen
stein
rivest
leiserson

 

Sample output

abdefgijkmhnopqtucsrlvwxyz

 


hide comments
neerajm: 2017-07-14 18:43:51

Somebody who has got it correct, please give the output of the following test case.
11
x
ax
ad
pa
pbd
pbm
pbe
pbeq
pbey
pbezy
pbezr
Thanks in advance

rasd: 2017-07-11 08:48:47

@ssuntik, yeah, you are right. I'll modify the answer

Last edit: 2017-07-11 13:54:02
ssunitk: 2017-07-09 16:53:57

abdefgijkmhnopqtucsrlvwxyz and abdefgijkmhucsrlnopqtvwxyz are two possible permutation of characters such that above given names are in lexicographic order , but by definition first one is lower than second and lowest among all. So i think answer for the first or sample test case should be first permutation.


Added by:Programming Club, IITK
Date:2017-07-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ESO207, IIT Kanpur Summer Semester 2017