Lexicographic Permutation Rank

Posted: 13 Jul, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja got holiday homework from his English teacher. His teacher gave him a string and told him to find the rank of the string if the string is sorted in lexicographical order.

Ninja is very new into programming, he didn’t know how to solve this question but he has to solve this question as this question has a very heavy weightage among all the questions given in holiday homework.

Ninja knows that you are a very good programmer who has practiced a lot of questions. Help Ninja!.

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.
Try Problem