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?
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|)$$$