[Doubt] k'th lexicographically smallest string

Revision en3, by Mikasa.Ackerman, 2023-03-07 02:18:16

I recently solved the follwing problem:
Given a string str, find it's rank in all of it's unique permutations.
Example: str = 'aba'
All unique permutations of aba (in sorted order) = ['aab', 'aba', 'baa']
Hence, the rank is 2.

I was wondering how can we solve the following (relevant) problem:
Given a string str and a rank r, find the permutation of str with given rank r.
So, for input str = 'baa' and r = 2, output will be 'aba'

If there are no repetations in string, I can use

this method

How do I handle repetations?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Mikasa.Ackerman 2023-03-07 02:18:16 1 (published)
en2 English Mikasa.Ackerman 2023-03-07 02:17:07 4
en1 English Mikasa.Ackerman 2023-03-07 02:16:41 704 Initial revision (saved to drafts)