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'