# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

#### 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.

Approach 2

The idea is to store the count of smaller elements in the right of each character in an auxiliary array in which the value at every index contains the count of smaller characters in the whole string.

**Approach:**

- First call the function ‘fact()’ passing ‘len’ as an argument, where ‘len’ is the length of the given string ‘S’ to calculate the factorial and store the value returned in a variable, say ‘factorial’.
- Initialize integer variable ‘rank’ to store the final answer and initialize it with value 1.
- Declare an auxiliary array, say ‘count’ of size 256 as there are 256 characters and initialize it with 0.
- Now fill the ‘count’ array such that count[i] contains the count of characters which are present in ‘S’ and smaller than ‘i’ where ‘i’ is the iterator pointer.
- 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 count the number of characters smaller than S[i] from S[i+1] to S[len - 1].
- Update ‘rank’ as rank = rank + count[S[i] - 1] * ‘factorial’.
- Now reduce the count of characters greater than S[i].

- Return ‘rank’ to the function.

SIMILAR PROBLEMS

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard

# Insertion Sort

Posted: 30 Nov, 2021

Difficulty: Easy

# Subarrays With Zero Sum

Posted: 1 Dec, 2021

Difficulty: Easy

# Find Student

Posted: 1 Dec, 2021

Difficulty: Easy

# Smaller Than Triplet Sum

Posted: 1 Dec, 2021

Difficulty: Moderate