# 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

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

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;
}
}