Photo Credit : Helen Morgan
The Third and final problem of the Facebook Qualification 2011 Round was Studious Student. The problem goes like this:
You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi
Analysis and Solution
This problem is a most confusing out of the lot. Me myself made a silly mistake while solving this problem. On first look it looks like the problem should get solved by sorting and joining the strings, but its not like that.
Consider this following input:
jibw ji jp bw jibw
By sorting and concatenate, the answer should be is:
However, lexicographically lowest possible string will be:
Notice in the above words, "ji" is the prefix of "jibw". The "sort and concatenate" method definitely does not work when there is a case where a word is a prefix of one or more other words.
Some of the contestants solved this problem with brute force, as input range was not that big. With M<=9 one could have only 9!= 362880 possible permutations. And answer can be obtained by sorting these permutations.
However, I didnâ€™t went this approach. I used python internal Sort function with custom compare. Here is my code