Lexicographic Rank of a String

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in companies
Urban Company (UrbanClap)WalmartNutanix

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.
Sample Input 1:
2
abc
cba
Sample Output 1:
1
6
Explanation for Sample Test Case 1:
All permutations with string abc in the lexicographical order will be “abc”, “acb”, “bac”, “bca”, “cab”, “cba”.

Test Case 1:
“abc” will have the rank 1.

Test Case 2:
“cba”  will have rank 6.
Sample Input 2:
2
coding
string
Sample Output 2:
100
598
Hint

Generate the permutations of the string smaller than the current character and then find the rank of the given string.

Approaches (2)
Permutations

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.
Time Complexity

O(N^2), where ‘N’ denotes the length of the given string ‘S’.

 

As we are making nested iterations to calculate the count of smaller characters in right of each character of the string. Therefore, overall time complexity will be O(N * N).

Space Complexity

O(1)

 

As constant space is used.

Code Solution
(100% EXP penalty)
Lexicographic Rank of a String
Full screen
Console