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

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!

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!

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

ReplyDeleteyour approach will fail in certain cases

ReplyDeleteRegards

In which cases this approach fails??

Deleteconsider the test case

Delete123 1231

Result : 1231123 & not 1231231

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

ReplyDeletecompare(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).

correct !!!

ReplyDelete