Блог пользователя Mikasa.Ackerman

Автор Mikasa.Ackerman, история, 20 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
20 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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