Mikasa.Ackerman's blog

By Mikasa.Ackerman, history, 20 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
20 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

https://leetcode.com/problems/numbers-at-most-n-given-digit-set/

I think this is a similar problem. You need to know how many strings you can generate and less than the given string.

Update

They are slightly different, you need to count how many strings can be formed (less than the given string) for each prefix of the strings that matches a prefix with the same length from the given string.

Frequency array & Counting unique permutations

Complexity: $$$O(|s|)$$$