Sorted Permutation Rank with Repeats

Given a string, find the rank of the string amongst its permutations sorted lexicographically. Note that the characters might be repeated. If the characters are repeated, we need to look at the rank in unique permutations. Look at the example for more details.

Example :

Input : 'aba'
Output : 2

The order permutations with letters 'a', 'a', and 'b' : 
aab
aba
baa

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

NOTE: 1000003 is a prime number NOTE: Assume the number of characters in string < 1000003

Explaination:

Let’s look at the string “settLe”. It has repetition(2 ‘e’ and 2 ‘t’) as well as upper case letter(‘L’). Total 6 characters and total number of permutations are 6!/(2!*2!). Now there are 3 characters(2 ‘e’ and 1 ‘L’) on the right side of ‘s’ which come before ‘s’ lexicographically. If there were no repetition then there would be 3*5! smaller strings which have the first character less than ‘s’. But starting from position 0, till end there are 2 ‘s’ and 2 ‘t'(i.e. repetations). Hence number of possible smaller permutations with first letter smaller than ‘s’ are (3*5!)/(2!*2!). Similarly if we fix ‘s’ and look at the letters from index 1 to end then there is 1 character(‘L’) lexicographically less than ‘e’. And starting from position 1 there are 2 repeated characters(2 ‘e’ and 2 ‘t’). Hence number of possible smaller permutations with first letter ‘s’ and second letter smaller than ‘e’ are (1*4!)/(2!*2!).

Similarly we can form the following table:

public class Solution {
    int MOD = 1000003;

    public int findRank(String A) {
        int size = A.length();
        char[] str = A.toCharArray();
        long ans = 1;
        for (int i = 0; i < size; i++) {
            long less_num = 0;
            // Number of elements less than str[i], on the right
            for (int j = i + 1; j < size; j++)
                if (str[j] < str[i])
                    less_num++;
            // Frequency array.
            int[] freq = new int[256];
            for (int j = i; j < size; j++)
                freq[str[j]]++;
            // Calculation of factorials in the denominator
            // because of repetitions
            long repeat = 1;
            for (int j = 0; j < 256; j++)
                repeat = (repeat * fact(freq[j])) % MOD;
            // Taking Modular Inverse using Fermat's little theorem.
            repeat = power(repeat, MOD - 2);
            // Calculations as shown in example
            long count = (fact(size - i - 1) * less_num) % MOD;
            count = (count * repeat) % MOD;
            // Adding in final answer
            ans = (ans + count) % MOD; 
        }
        return (int) ans;
    }

    // Power function -> X^Y
    public long power(long x, long y) {
        long res = 1;
        while (y > 0) {
            if (y % 2 != 0)
                res = (res * x) % MOD;
            x = (x * x) % MOD;
            y = y / 2;
        }
        return res;
    }

    // Factorial Function
    public long fact(int n) {
        if (n == 0 || n == 1)
            return 1;
        long ans = 1;
        while (n > 1) {
            ans = (ans * n) % MOD;
            n--;
        }
        return ans;
    }
}