# 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<br>

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<br>

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

```java
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);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/maths/untitled.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.