Sorted Permutation Rank

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

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

思路:

        
                        3  2  1  0
            abcd = 0, 0, 0, 0
            abdc = 0, 0, 1, 0
            acbd = 0, 1, 0, 0
            acdb = 0, 1, 1, 0
            adbc = 0, 2, 0, 0
            adcb = 0, 2, 1, 0
            bacd = 1, 0, 0, 0
         
我们记录每一位比他小的个数，比如对于adcb，在a没有数能比他小，在d，能找到2个比他小的数(b, c)，在c，能找到一个比他小的数(b)，d是最后一位数，所以没有比他小的数，因为已经没有数能给我们选择了。
每有一个比当前数小的数，即代表在这一位，能有n * x!的组合的数比当前数小（n = 有几个小的数，x = 当前的index），比如对于d，有bc比他小（n = 2, x = 2），所以有abcd, abdc, acbd, acdb比adXX要小，2 * 2!
我们可以用binary index tree 来记录比当前位小的数。

Solution:

Time: O (n)
Space: O (n)

public class Solution {
    public static class BIT {
        int[] arr;
        
        public BIT(int n) {
            this.arr = new int[n + 1];
        }
        
        public void update(int i, int v) {
            // update nodes that include i in left subtree
            i = i + 1;
            while (i <= this.arr.length) {
                this.arr[i] += v;
                i += i & (-i);
            }
        }
        
        public int sum(int i) {
            // sum up left sub trees smaller than i
            int sum = 0;
            i = i + 1;
            while (i > 0) {
                sum += this.arr[i] % 1000003;
                i -= i & (-i);
            }
            return sum;
        }
    }
    
    private int[] factorial(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 1;
        for (int i = 1; i < arr.length; i ++) {
            arr[i] = (arr[i - 1] * i) % 1000003; 
        }
        return arr;
    }
    
    public int findRank(String A) {
        BIT bit = new BIT(128);
        int[] factorial = factorial(A.length()); 
        char[] arr = A.toCharArray();
        /*
                   3  2  1  0
            abcd = 0, 0, 0, 0
            abdc = 0, 0, 1, 0
            acbd = 0, 1, 0, 0
            acdb = 0, 1, 1, 0
            adbc = 0, 2, 0, 0
            adcb = 0, 2, 1, 0
            bacd = 1, 0, 0, 0
         
        */
        for (int i = 0; i < arr.length; i ++) {
            int c = arr[i];
            bit.update(c, 1);
        }
        int rank = 1;
        for (int i = 0; i < arr.length; i ++) {
            int c = arr[i];
            int smallerCount = bit.sum(c) - 1;
            // System.out.println(arr[i] + " " + smallerCount + " " + factorial[arr.length - i - 1]);
            rank += smallerCount * factorial[arr.length - i - 1];
            bit.update(c, -1);
        }
        return rank % 1000003;
    }
}