First!
Time limit1sMemory limit128 MB
Given up to 30000 strings, find every string that can become lexicographically smallest under some permutation of the 26-letter alphabet.
- Level
Hard8 of 10
- Topics
- String, Trie, Graph, Topological sort
- Solved
- No attempts yet
Problem
Bessie is playing with strings. She noticed that by changing the order of the alphabet she can make some strings come before all the others in lexicographic (dictionary) order.
For example, given the strings omm, moo, mom, and ommnom, she can make mom appear first using the standard alphabet, and she can make omm appear first using the alphabet abcdefghijklonmpqrstuvwxyz. However, no ordering of the alphabet makes moo or ommnom appear first.
Help Bessie by determining which of the input strings can be made lexicographically first by rearranging the order of the alphabet.
To decide whether string comes before string , find the first index at which they differ. If no such index exists, then comes before when is shorter than . Otherwise, comes before when appears earlier in the alphabet than .
Input
- Line 1: A single integer (), the number of strings.
- Lines 2 through : Each line contains one non-empty string. The total number of characters across all strings is at most . Every character is a lowercase letter from
atoz. No two input strings are identical.
Output
- Line 1: A single integer , the number of strings that can be made lexicographically first.
- Lines 2 through : The qualifying strings, printed in the same order in which they appear in the input.
Hint
With the standard alphabet, mom is the lexicographically smallest of the four sample strings, so mom can be first. Using the alphabet abcdefghijklonmpqrstuvwxyz (where o precedes n), omm becomes smallest, so omm can be first. No reordering of the alphabet can make moo or ommnom first, so exactly two strings qualify.