# Calculate rank of given string among all its lexicographically sorted permutations

Given a string, calculate its rank among all its lexicographically sorted permutations.

For example, consider below lexicographically sorted permutations –

CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Lexicographic rank of the string DCBA is 24
Lexicographic rank of the string BDAC is 11

A simple solution would to use std::next_permutation that generates the next greater lexicographic permutation of a string. The idea is to sort the string in ascending order and calculate repeatedly calculate lexicographic next permutation till current permutation becomes equal to the given string.

Output:

Lexicographic Rank of DCBA is 24

Note that we can also use std::prev_permutation in place of std::next_permutation that generates the next smaller lexicographic permutation of a string. The implementation can be seen here.

The time complexity of above solution is O(n.n!) and auxiliary space used by the program is O(1).

We can improve worst case time complexity to O(n2) by finding the number of characters are ranked before the current character in the string. Let c[i] denotes count of smaller characters than str[i] to the right of index i. Then, for the string of length n

• There will be c[0]*(n-1)! permutations ranked above first character in the string.
• There will be c[1]*(n-2)! permutations ranked above second character in the string.
• There will be c[2]*(n-3)! permutations ranked above third character in the string and so on..

Below is C++/Java implementation based on above idea –

## Java

Output:

Lexicographic Rank of DCBA is 24

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).