Sorted Permutation Rank

Given a string, find the rank of the string amongst its permutations sorted lexicographically. Assume that no characters are repeated.

Example :

Input : 'acb'
Output : 2

The order permutations with letters 'a', 'c', and 'b' : 
abc
acb
bac
bca
cab
cba

The answer might not fit in an integer, so return your answer % 1000003

Explaination:

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

R X X X X X I X X X X X N X X X X X G X X X X X

Now let us Fix S’ and find the smaller strings starting with ‘S’.

Repeat the same process for T, rank is 4*5! + 4*4! +…

Now fix T and repeat the same process for R, rank is 4*5! + 4*4! + 3*3! +…

Now fix R and repeat the same process for I, rank is 4*5! + 4*4! + 3*3! + 1*2! +…

Now fix I and repeat the same process for N, rank is 4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…

Now fix N and repeat the same process for G, rank is 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0!

Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597

Note that the above computations find count of smaller strings. Therefore rank of given string is count of smaller strings plus 1. The final rank = 1 + 597 = 598

public class Solution {
    int MOD = 1000003;

    public int findRank(String str) {
        int prefixFreqSum[] = GetFrequencies(str);
        int ans = 1;
        for (int i = 0; i < str.length(); i++) {
            int fact = Factorial(str.length() - i - 1);
            ans += ((fact % MOD) * (prefixFreqSum[str.charAt(i) - 1] % MOD)) % MOD;
            UpdateFrequency(prefixFreqSum, str.charAt(i));
        }
        return ans % MOD;
    }

    public void UpdateFrequency(int arr[], char ch) {
        for (int i = ch; i < 256; i++)
            arr[i]--;
    }

    public int[] GetFrequencies(String str) {
        int prefixFreqSum[] = new int[256];
        for (int i = 0; i < str.length(); i++)
            prefixFreqSum[str.charAt(i)]++;
        for (int i = 1; i < 256; i++)
            prefixFreqSum[i] += prefixFreqSum[i - 1];
        return prefixFreqSum;
    }

    public int Factorial(int n) {
        return (n <= 1 ? 1 : ((n % MOD) * (Factorial(n - 1) % MOD)) % MOD);
    }
}