Search

Sorted Permutation Rank with Repeats InterviewBit Solution

Problem: Sorted Permutation Rank with Repeats


Problem Description:

Given a string, find the rank of the string amongst its permutations sorted lexicographically.

Note that the characters might be repeated. If the characters are repeated, we need to look at the rank in unique permutations.

Look at the example for more details.


Example :

Input : 'aba' Output : 2  
The order permutations with letters 'a', 'a', and 'b' :  
    aab 
    aba 
    baa

The answer might not fit in an integer, so return your answer % 1000003.



Approach


Let's try to break this problem, character by character.

So let's take an example: 

S = "bcab"

So for char S[0] = 'b', it has one character smaller than itself, and that is S[2] = 'a', so if we swap 'b' with 'a', then it is obvious that in lexicographical order, the new string will come before our current string.


Before starting, let's recall the formula for the number of permutation with repetition.

P = N! / (p1! * p2! * p3! ... )

Where p1, p2, p3 is the frequency of the 1st, 2nd & 3rd element, and so on.


The denominator part can cause overflow, but we have to take the mod. So we can use modular multiplicative inverse.

(1/A) % MOD = A ^ (MOD - 2) % MOD

So now, let's check for every position.

Input: S = "bcab"
Index 0: 
    S[0] = 'b', characters lesser than S[0] are, S[2] = 'a'.
    And freq['a'] = 1, freq['b'] = 2, freq['c'] = '1'. (S[0..3] = "bcab")
    So total permutation = (4-1)! / (1! * 2! * 1!) = 3.
    
    So there are three unique strings that can be made by placing, 
    S[0] = 'a'. And these strings are, "abbc", "abcb" & "acbb".
Index 1: 
    Now we don't have to check for 0th position, so we only consider     indexes from, 1 to 3.
    
    S = "bcab"
    S[1] = 'c', characters lesser than S[1] are, S[2] = 'a' and S[3] = 'b'.
    And freq['a'] = 1, freq['b'] = 1, freq['c'] = '1'. (S[1..3] = "cab")
    -> freq['b'] is 1, because, we are not considering indexes below the current index.
    
    So permutation  = (4-2)! / (1! * 1! * 1!) = 2.
    But we have two characters that are lesser than 'c', so we must multiply 2 with the our current answer.
    
    So total permutation = 2*2 = 4.
    Some of the examples are, "babc", "bbac", .....
Index 2:
    Now, S[2] = 'a', there is no characters less than 'a'.
    
    Since there is no character less than 'a', 
    So total permutation = 0.
Index 3:
    Same as in case of Index 2. 
    So total permutation = 0.

Adding all the results of the index will give total number of unique strings that are smaller than the current string, lexicographically. So we have to add 1 to this to get rank of our string.

Ans = (3 + 4 + 0 + 0) + 1 = 8.


Time & Space Complexity:

Time Complexity: O(N^2)

- For every index we are traversing the string, to find the frequency and the number of character lesser than the current one.

Space Complexity: O(1)

- Apart from the space taken by our input array, we have taken the constant amount of space, independent of the size of the string.




Solution:


Code in C++


Tags: