Formatted question description: https://leetcode.ca/all/1830.html

# 1830. Minimum Number of Operations to Make String Sorted

## Level

Hard

## Description

You are given a string `s`

(**0-indexed**). You are asked to perform the following operation on `s`

until you get a sorted string:

- Find
**the largest index**`i`

such that`1 <= i < s.length`

and`s[i] < s[i - 1]`

. - Find
**the largest index**`j`

such that`i <= j < s.length`

and`s[k] < s[i - 1]`

for all the possible values of`k`

in the range`[i, j]`

inclusive. - Swap the two characters at indices
`i - 1`

and`j`

. - Reverse the suffix starting at index
`i`

.

Return *the number of operations needed to make the string sorted*. Since the answer can be too large, return it **modulo** `10^9 + 7`

.

**Example 1:**

**Input:** s = “cba”

**Output:** 5

**Explanation:** The simulation goes as follows:

Operation 1: i=2, j=2. Swap s[1] and s[2] to get s=”cab”, then reverse the suffix starting at 2. Now, s=”cab”.

Operation 2: i=1, j=2. Swap s[0] and s[2] to get s=”bac”, then reverse the suffix starting at 1. Now, s=”bca”.

Operation 3: i=2, j=2. Swap s[1] and s[2] to get s=”bac”, then reverse the suffix starting at 2. Now, s=”bac”.

Operation 4: i=1, j=1. Swap s[0] and s[1] to get s=”abc”, then reverse the suffix starting at 1. Now, s=”acb”.

Operation 5: i=2, j=2. Swap s[1] and s[2] to get s=”abc”, then reverse the suffix starting at 2. Now, s=”abc”.

**Example 2:**

**Input:** s = “aabaa”

**Output:** 2

**Explanation:** The simulation goes as follows:

Operation 1: i=3, j=4. Swap s[2] and s[4] to get s=”aaaab”, then reverse the substring starting at 3. Now, s=”aaaba”.

Operation 2: i=4, j=4. Swap s[3] and s[4] to get s=”aaaab”, then reverse the substring starting at 4. Now, s=”aaaab”.

**Example 3:**

**Input:** s = “cdbea”

**Output:** 63

**Example 4:**

**Input:** s = “leetcodeleetcodeleetcode”

**Output:** 982157772

**Constraints:**

`1 <= s.length <= 3000`

`s`

consists only of lowercase English letters.

## Solution

This problem is to find the index of `s`

in the lexicographical order of all permutations of `s`

.

The solution is to count the number of permutations that are lexicographically smaller than `s`

.

```
class Solution {
static final int MODULO = 1000000007;
public int makeStringSorted(String s) {
int length = s.length();
int[] f = new int[26];
int[] p = new int[length + 1];
int[] all = new int[length + 1];
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
f[c - 'a']++;
}
p[1] = 1;
all[1] = 1;
for (int i = 2; i <= length; i++) {
int temp = power(i, MODULO - 2);
p[i] = (int) ((long) p[i - 1] * temp % MODULO);
all[i] = (int) ((long) all[i - 1] * i % MODULO);
}
int operations = 0;
for (int i = 0; i < length; i++) {
int left = length - 1 - i;
int index = s.charAt(i) - 'a';
for (int j = 0; j < index; j++) {
int up = all[left];
if (f[j] != 0) {
f[j]--;
for (int k = 0; k < 26; k++) {
if (f[k] != 0)
up = (int) ((long) up * p[f[k]] % MODULO);
}
operations = (operations + up) % MODULO;
f[j]++;
}
}
f[index]--;
}
return operations;
}
public int power(int x, int n) {
int power = 1;
while (n > 0) {
if (n % 2 == 1)
power = (int) ((long) power * x % MODULO);
x = (int) ((long) x * x % MODULO);
n /= 2;
}
return power;
}
}
```