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'