Lexicographic Permutation Rank
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

Question

Lexicographic Permutation Rank

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.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

As constant space is used.

Time Complexity: O(n^2)Explanation:

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

Python (3.5)

'''

    Time Complexity: O(N * N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

'''



#MAX = 256



# Function to calculate factorial of 'n'.



def fact(n):

    if n <= 1:

        return 1



    return n * fact(n - 1)



# Function to count smaller characters on right of current element.

def smallRight(S, low, high):

    count = 0

    for i in range(low + 1, high + 1):

        if ord(S[i]) < ord(S[low]):

            count += 1

        

    return count







def lexiRank(S):

    l = len(S)

    factorial = fact(l)

    rank = 1



    count = 0



    for i in range(len(S)):

        factorial = factorial // (l - i)



        # Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].



        count = smallRight(S, i, l - 1)



        rank = rank + (count * factorial)



    return rank

Java (SE 1.8)

/*

    Time Complexity: O(N * N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution {



    // Function to calculate factorial of 'n'.

    private static long fact(int n) {

        if (n <= 1) {

            return 1;

        }



        return n * fact(n - 1);

    }





    // Function to count smaller characters on right of current element.

    private static int SmallRight(String S, int low, int high) {

        int count = 0;



        for (int i = low + 1; i <= high; i++) {

            if (S.charAt(i) < S.charAt(low)) {

                count = count + 1;

            }

        }



        return count;

    }





    public static long lexicRank(String S) {



        int len = S.length();

        long factorial = fact(len);

        long rank = 1;

        int count;



        for (int i = 0; i < len; ++i) {

            factorial = factorial / (len - i);



            // Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].

            count = SmallRight(S, i, len - 1);



            rank = rank + (count * factorial);

        }



        return rank;

    }

}

C++ (g++ 5.4)

/*

    Time Complexiity: O(N * N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

*/



// Function to calculate factorial of 'n'.

unsigned long long fact(int n)

{

    if(n <= 1)

    {

        return 1;

    }



    return n * fact(n - 1);

}



// Function to count smaller characters on right of current element.

int SmallRight(string S, int low, int high)

{

	int count = 0;



	for (int i = low + 1; i <= high; i++)

    {

		if (S[i] < S[low])

        {

			count = count + 1;

        }

    }



	return count;

}



unsigned long long lexicRank(string S)

{

	int len = S.length();

	unsigned long long factorial = fact(len);

	unsigned long long rank = 1;

	int count;



	for (int i = 0; i < len; ++i) 

    {

		factorial = factorial / (len - i);



		// Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].

		count = SmallRight(S, i, len - 1);



		rank = rank + (count * factorial);

	}



	return rank;

}

Accepted Answer

Optimised Approach

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.

Space Complexity: O(1)Explanation:

O(1)

As constant space is used for storing the count of smaller characters in the whole string. Therefore, overall space complexity will be O(1).

Time Complexity: O(n)Explanation:

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

As we are traversing the whole string in linear time . Therefore, overall time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution {



    private static int MAX = 256;

    // Function to calculate factorial of 'n'.

    private static long fact(int n) {

        if (n <= 1) {

            return 1;

        }



        return n * fact(n - 1);

    }





    // Function to remove a character 'c' from count[] array.

    private static void removeCount(int count[], char c) {



        for (int i = c; i < MAX; i++) {

            --count[i];

        }

    }





    public static long lexicRank(String S) {



        int len = S.length();

        long factorial = fact(len);

        long rank = 1;



        // all elements of count[] are initialized with 0

        int[] count = new int[MAX];

        Arrays.fill(count, 0);



        /*

            Fill the count array such that count[i] contains count

            of characters which are present in S and are smaller than i.

        */

        for (int i = 0; i < S.length(); ++i) {

            ++count[S.charAt(i)];

        }



        for (int i = 1; i < MAX; ++i) {

            count[i] = count[i] + count[i - 1];

        }



        for (int i = 0; i < len; ++i) {

            factorial = factorial / (len - i);



            // Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].

            rank = rank + count[S.charAt(i) - 1] * factorial;



            // Reduce count of characters greater than S[i].

            removeCount(count, S.charAt(i));

        }



        return rank;

    }

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

'''



#MAX = 256



# Function to calculate factorial of 'n'.



def fact(n):

    if n <= 1:

        return 1



    return n * fact(n - 1)



# Function to remove a character 'c' from count[] array.



def removeCount(count, c):

    for i in range(ord(c), 256):

        count[i] -= 1



def lexiRank(S):

    l = len(S)

    factorial = fact(l)

    rank = 1



    count = [0 for i in range(256)]



    '''

        Fill the count array such that count[i] contains count

        of characters which are present in S and are smaller than i.

    '''



    for i in range(len(S)):

        count[ord(S[i])] += 1

    

    for i in range(1, 256):

        count[i] = count[i] + count[i - 1]



    for i in range(l):

        factorial = factorial // (l - i)



        # Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].

        rank = rank + count[ord(S[i]) - 1] * factorial



        # Reduce count of characters greater than S[i].

        removeCount(count, S[i])

    

    return rank

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' denotes the length of the given string.

*/



#define MAX 256



// Function to calculate factorial of 'n'.

unsigned long long fact(int n)

{

    if(n <= 1)

    {

        return 1;

    }



    return n * fact(n - 1);

}



// Function to remove a character 'c' from count[] array.

void removeCount(int count[], char c)

{

	for (int i = c; i < MAX; i++)

    {

		--count[i];

    }

}



unsigned long long lexicRank(string S)

{

	int len = S.length();

	unsigned long long factorial = fact(len);

	unsigned long long rank = 1;



	// all elements of count[] are initialized with 0

	int count[MAX] = { 0 };



	/*

        Fill the count array such that count[i] contains count

        of characters which are present in S and are smaller than i.

    */

    for (int i = 0; S[i]; ++i)

    {

		++count[S[i]];

    }



	for (int i = 1; i < MAX; ++i)

    {

		count[i] = count[i] + count[i - 1];

    }



	for (int i = 0; i < len; ++i) 

    {

		factorial = factorial / (len - i);



		// Counting number of characters smaller than S[i] from S[i + 1] to S[len - 1].

		rank = rank + count[S[i] - 1] * factorial;



		// Reduce count of characters greater than S[i].

		removeCount(count, S[i]);

	}



	return rank;

}

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:

Input Format:

Output Format:

Note:

Constraints:

Top Nutanix Mts1 interview questions & answers

Popular interview questions of Mts1