> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/maths/sorted-permutation-rank-with-repeats.md).

# 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&#x20;

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

![](https://media.geeksforgeeks.org/wp-content/cdn-uploads/lexographic-rank-of-string.jpg)

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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/sorted-permutation-rank-with-repeats.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.