# Lexicographic Permutation Rank

Posted: 13 Jul, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note:

``````There will only be distinct characters in the given string.
``````

#### Input Format:

``````First line contains an integer ‘T’ denoting the number of test cases.

First and the only line of the test case contains a string ‘S’.
``````

#### Output Format:

``````Output contains an integer ‘X’ denoting the Lexicographic Permutation Rank of the given string.
``````

#### Note:

``````You don’t need to print anything, it has already been taken care of. Just implement the given function.
``````

#### Constraints:

``````1 <= T <= 25
1 <= |S| <= 20
‘a’ <= S[i] <= ‘z’

Time Limit: 1 sec.
``````
Approach 1

Permutation :

• Let the given string be “CODING”. In the input string, ‘C’ is the first character. There are a total of 6 characters and 0 of them are smaller than ‘C’. So there can be 0 * 5! smaller strings where the first character is smaller than ‘C’.
• Now let us Fix ‘C’ and find the smaller strings starting with ‘C’.
• Repeat the same process for ‘O’, rank is 0*5! + 4*4! +…
• Now fix ‘O’ and repeat the same process for ‘D’, rank is 0*5! + 4*4! + 0*3! +…
• Now fix ‘D’ and repeat the same process for ‘I’, rank is 0*5! + 4*4! + 0*3! + 1*2! +…
• Now fix ‘I’ and repeat the same process for ‘N’, rank is 0*5! + 4*4! + 0*3! + 1*2! + 1*1! +…
• Now fix ‘N’ and repeat the same process for ‘G’, rank is 0*5! + 4*4! + 0*3! + 1*2! + 1*1! + 0*0!
• Rank = 0*5! + 4*4! + 0*3! + 1*2! + 1*1! + 0*0! = 99

The above computations find the count of smaller strings. Therefore the rank of a given string “CODING” is the count of smaller strings plus 1. The final rank = 1 + 99 = 100.

Approach :

• First make a function, say ‘fact()’ taking integer ‘n’ as a parameter which will return the factorial of the integer ‘n’.
• Now make a function, say ‘smallRight()’ taking string ‘S’, integer variable ‘low’ representing lower index and integer variable ‘high’ representing higher index as parameters to calculate count of smaller characters in right.
• Declare a variable, say ‘count’ to store the count of smaller characters in right.
• Iterate from ‘low’ + 1 to ‘high’ with the help of iterator pointer ‘i’.
• If a character, S[i] is less than S[low] then increment ‘count’.
• Return ‘count’ to the function.
• Inside the given function:
• First calculate the factorial of the length of the string by calling function ‘fact()’ passing length of the string as its argument and store the value returned in a variable, say ‘factorial’.
• Now declare a variable, say ‘rank’ to store the final answer and initialize it with value 1.
• Now iterate over the whole string with iterator pointer ‘i’.
• Make ‘factorial’ as factorial = factorial / len - i. Where ‘len’ denotes the length of the string ‘S’.
• Now call the function ‘smallRight()’ passing string ‘S’, ‘i’ and ‘len’ - 1 as its arguments in place of ‘S’, ‘low’ and ‘high’ respectively and store the result returned in a variable, say ‘count’.
• The above step is done to count the characters smaller than S[i] from S[i+1] to S[len - 1].
• Now make ‘rank’ as ‘rank’ = ‘rank’ + ‘count’ * ‘factorial’.
• Return ‘rank’ to the function as the final answer.