Find Kth lexographically smallest string

Question

Given N A'sand N B's How to find Kth lexographically smallest string of all the strings of length 2*N.

Like if N=2 It means we have 2A and 2B then if we need to find say 2(=K) smallest lexographically smallest string then answer is "ABBA".

Explanation :

0.AABB
1.ABAB
2.ABBA
3.BAAB
4.BABA
5.BBAA

One way is to just simply find all the strings and sort them and then find kth smallest string.But is their a better way to do it ?

possible duplicate of [Compute rank of a combination?](http://stackoverflow.com/questions/3143142/compute-rank-of-a-combination) — David Eisenstat, Aug 26 '14 at 20:47
It's not different at all if you read it and think about it for more than a minute. — David Eisenstat, Aug 26 '14 at 20:52
Does this help? http://stackoverflow.com/questions/24752016/finding-permutation-of-a-set-of-0-and-1-given-index-with-on/24770852#24770852 — גלעד ברקן, Aug 26 '14 at 23:33
Isn't this question from an on-going contest at Hackerrank.com? — Abhishek Bansal, Aug 27 '14 at 05:00

score 0 · Accepted Answer · answered Aug 27 '14 at 07:54

First let us start from left. You have N A's and N B's. First compute the number of strings possible with A as their first character. It is (2n-1)!/((n-1)!(n)!) If this value is greater than K, then our string will start with K otherwise it will start with B. Now, to move on we have two cases

Case1: If it starts with A, then the number of A's to check in next step will decrease by 1. And we will check for (2n-2)!/((n-2)!(n!)) Value of K need not be updated.

Case2: If it starts with B, then the number of B's to check in next step will decrease by 1. And we will check for (2n-2)!/((n-1)!(n-1)!) Value of 1 will be updated to K - (2n-1)!/((n-1)!(n)!) and we proceed with new values.

Complexity issues: We need not compute the factorials every time newly. Since we see that the factorial in numerator is decreasing consistently we can divide it with (2n - stepNo) and get next step's numerator. Similarly for either of the denominators.

Find Kth lexographically smallest string

1 Answers1