Question

link

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

For example, rank of “abc” is 1, rank of “acb” is 2, and rank of “cba” is 6.

Solution

Let the given string be “STRG”. In the input string, ‘S’ is the first character. There are total 4 characters and 2 of them are smaller than ‘S’. So there can be 2 * 3! smaller strings where first character is smaller than ‘S’, like following:

G X X X
R X X X

Repeat the same process for T, and we get:

Rank = 2*3! + 2*2! + 1*1! + 0*0! = 17

Code

public int getRank(String input) {
    if (input == null || input.length() == 0) {
        return 0;
    }
    input = input.toUpperCase();
    return helper(input) + 1;
}

public int helper(String input) {
    if (input == null || input.length() == 0) {
        return 0;
    }
    char headChar = input.charAt(0);
    int countSmallerThanHead = 0;
    for (char ch : input.toCharArray()) {
        if (ch < headChar) {
            countSmallerThanHead++;
        }
    }
    return countSmallerThanHead * Common.factorial(input.length() - 1)
            + helper(input.substring(1));
}