Saturday, January 29, 2011

Lexicographically smallest string

Given a group of strings, find a string by concatenating all the strings in any order which produces the lexicographically smallest string.
For e.g strings are acc bcc abb
So the string formed should be abbaccbcc

Approach:

By looking at the problem the most quick and easy solution seems to sort the strings and concat them.
But wait, will it really work?
Lets say, strings are aba and ab 
With the above approach the solution would be ababa
But infact there exists a lexicographically smaller string and that is abaab.

So what went really wrong? Take a minute to think it through and how to overcome it.


The anomaly in the  solution was observed when one of the strings is prefix of the other, like ab is prefix for aba.
In such cases the suffix actually decides the ordering of the strings.
So how do we resolve this ?

An easy operation would be to check if 
a + b < b + a


So we indeed do a sorting but with the below sorting function :)

int compare(string a, string b) {
    return (a+b).compareTo(b + a);
}

Then concat the resultant sorted array and you have your result!

6 comments :

  1. Sort the strings and concatenate in order, going from the lexically smallest to lexically largest.

    ReplyDelete
  2. your approach will fail in certain cases

    Regards

    ReplyDelete
    Replies
    1. In which cases this approach fails??

      Delete
    2. consider the test case
      123 1231
      Result : 1231123 & not 1231231

      Delete
  3. lexicographical sorting is not enough. you should make a specific comparison function when sorting. something like:

    compare(String a, String b){
    return (a+b).compareTo(b+a);
    }

    a+b is the concatenation of a and b and compareTo is a lexographic comparison. now sort and you have a O(n log n) solution.

    you can also solve recursively for the n-1 first strings and for the n-th you try to include it in every possible place in the answer of the n-1 first string, picking the best place. this approach would take O(n^2).

    ReplyDelete