# Minimum Number of Operations to Make String Sorted
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-string-sorted
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** String
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
You are given a string `s` (**0-indexed**)​​​​​​. You are asked to perform the following operation on `s`​​​​​​ until you get a sorted string:

1. Find **the largest index** `i` such that `1 <= i < s.length` and `s[i] < s[i - 1]`.
2. 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.
3. Swap the two characters at indices `i - 1`​​​​ and `j`​​​​​.
4. 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** `109 + 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".

**Constraints:**

* `1 <= s.length <= 3000`
* `s`​​​​​​ consists only of lowercase English letters.

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We start with the given string and repeatedly apply the "previous permutation" operation until the string becomes sorted. We count the number of operations performed.
**Time:** O(K * N), where `N` is the length of the string and `K` is the total number of operations. `K` can be very large, making this approach impractical. · **Space:** O(N) to store the character array.
**Pros:** Simple to understand and implement as it directly follows the problem description.
**Cons:** Extremely inefficient. The number of operations can be astronomically large (related to `n!`), causing the simulation to be too slow for the given constraints (`n` up to 3000). This will result in a Time Limit Exceeded (TLE) error.
### Explanation
The algorithm involves a loop that continues as long as the string is not sorted. Inside the loop, we perform one operation as defined:
1. Find the largest index `i` where `s[i] < s[i-1]`. This identifies the pivot point for generating the previous permutation.
2. Find the largest index `j` in the suffix `s[i:]` such that `s[j] < s[i-1]`. This finds the character to swap with the pivot.
3. Swap the characters at `i-1` and `j`.
4. Reverse the suffix of the string starting from index `i`.
We maintain a counter which is incremented in each iteration of the loop. The simulation stops when the string is lexicographically sorted, and we return the final count. Since the string is modified in place, we convert it to a character array for easier manipulation.
```java
class Solution {
    public int makeStringSorted(String s) {
        long count = 0;
        long MOD = 1_000_000_007;
        char[] chars = s.toCharArray();
        int n = s.length();

        while (true) {
            int i = n - 1;
            while (i > 0 && chars[i] >= chars[i - 1]) {
                i--;
            }

            if (i == 0) {
                // String is sorted
                break;
            }

            int pivot = i - 1;
            int j = n - 1;
            while (j >= i && chars[j] >= chars[pivot]) {
                j--;
            }
            
            swap(chars, pivot, j);
            reverse(chars, i, n - 1);
            
            count = (count + 1) % MOD;
        }
        return (int) count;
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    private void reverse(char[] chars, int start, int end) {
        while (start < end) {
            swap(chars, start, end);
            start++;
            end--;
        }
    }
}
```
### Algorithm
- `Initialize count = 0.`
- `Convert the input string s to a character array chars.`
- `Start an infinite loop:`
    - `Find the largest index i such that 1 <= i < n and chars[i] < chars[i-1].`
    - `If no such i exists, the string is sorted. Break the loop.`
    - `Find the largest index j such that i <= j < n and chars[j] < chars[i-1].`
    - `Swap chars[i-1] and chars[j].`
    - `Reverse the subarray of chars from index i to the end.`
    - `Increment count (modulo 10^9 + 7).`
- `Return count.`

## Combinatorial Counting
This approach reframes the problem from simulation to a mathematical counting problem. The number of operations required to sort the string is equal to the number of unique permutations of its characters that are lexicographically smaller than the given string `s`. We can calculate this count by iterating through the string from left to right.
**Time:** O(N * A), where `N` is the string length and `A` is the alphabet size (26). Precomputation takes O(N * log(MOD)). · **Space:** O(N + A) for storing factorials, their inverses, and frequency counts, where A is the alphabet size.
**Pros:** Significantly more efficient than simulation.; Avoids the TLE issue by using a mathematical formula instead of step-by-step transformation.; Correctly handles strings with duplicate characters.
**Cons:** The calculation of the count of smaller characters is done in `O(A)` inside the main loop, leading to an `O(N * A)` complexity. This can be further optimized.
### Explanation
The core idea is to count, for each position `i` from `0` to `n-1`, how many smaller permutations we can form by choosing a different character for this position. We iterate through the string `s` from left to right. At each position `i`, we consider the suffix of the string starting at `i`. Let the set of available characters for the suffix be `C` with frequencies `freq`, and the length of the suffix be `m = n - i`. We count how many characters in `C` are smaller than `s[i]`. Let this be `count_smaller`. The number of permutations of the remaining `m-1` characters is `(m-1)! / (product of freq[c]!)`. The total contribution from position `i` is `count_smaller * (m-1)! / (product of freq[c]!)`. We sum these contributions for all `i`. To handle large numbers and divisions, all calculations are done modulo `10^9 + 7`, requiring precomputed factorials and their modular inverses.
```java
class Solution {
    long[] fact;
    long[] invFact;
    long MOD = 1_000_000_007;

    public int makeStringSorted(String s) {
        int n = s.length();
        precomputeFactorials(n);

        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        long permsDenominatorInv = 1;
        for (int count : freq) {
            permsDenominatorInv = (permsDenominatorInv * invFact[count]) % MOD;
        }

        long totalOps = 0;
        for (int i = 0; i < n; i++) {
            int remainingChars = n - i;
            int charCode = s.charAt(i) - 'a';

            long countSmaller = 0;
            for (int j = 0; j < charCode; j++) {
                countSmaller += freq[j];
            }

            if (countSmaller > 0) {
                long term = (fact[remainingChars - 1] * countSmaller) % MOD;
                long contribution = (term * permsDenominatorInv) % MOD;
                totalOps = (totalOps + contribution) % MOD;
            }

            permsDenominatorInv = (permsDenominatorInv * freq[charCode]) % MOD;
            freq[charCode]--;
        }

        return (int) totalOps;
    }

    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- `Precompute factorials and their modular inverses up to n.`
- `Calculate the frequency of each character in the input string s.`
- `Calculate an initial denominator term: product of invFact[freq[c]] for all c.`
- `Initialize total_operations = 0.`
- `Iterate i from 0 to n-1:`
    - `Let m = n - i be the number of remaining characters.`
    - `Count the number of available characters smaller than s[i] by iterating through the frequency array. Let this be count_smaller.`
    - `Calculate the contribution for this step: count_smaller * (m-1)! * (current denominator inverse).`
    - `Add this contribution to total_operations (modulo 10^9 + 7).`
    - `Update the denominator inverse for the next iteration by multiplying by the current frequency of s[i].`
    - `Decrement the frequency of character s[i].`
- `Return total_operations.`

## Combinatorial Counting with Fenwick Tree
This approach builds upon the combinatorial counting method by optimizing the two main operations inside the loop: counting smaller characters and calculating the permutation denominator. A Fenwick Tree (or Binary Indexed Tree) is used to speed up the query for smaller character counts, and the denominator term is updated incrementally.
**Time:** O(N * log(A)), where `N` is the string length and `A` is the alphabet size. Precomputation takes O(N + A*logA). · **Space:** O(N + A) for factorials and the Fenwick Tree.
**Pros:** Most efficient approach.; Reduces the complexity of each step in the main loop from `O(A)` to `O(log A)`.
**Cons:** More complex to implement due to the use of a Fenwick Tree.; The underlying mathematical concept is less direct than simulation.
### Explanation
The overall logic is the same as the previous combinatorial approach. The key difference lies in the implementation details for efficiency.
- **Fenwick Tree for Smaller Count**: We use a Fenwick Tree of size 26 to maintain the character frequencies. To find the number of available characters smaller than `s[i]`, we can query the prefix sum in the Fenwick Tree up to `s[i] - 'a'`. This operation takes `O(log A)` time, where `A` is the alphabet size. After processing `s[i]`, we update the Fenwick Tree by decrementing the count for `s[i]`, which also takes `O(log A)`.
- **Incremental Denominator Update**: Instead of recomputing the product of inverse factorials in each step, we update it incrementally. When we use up a character `c`, its frequency `f_c` becomes `f_c - 1`. The denominator inverse term gets multiplied by `f_c`. This update takes `O(1)` time.
By combining these two optimizations, the work inside each iteration of the main loop is reduced significantly.
```java
class Solution {
    long[] fact;
    long MOD = 1_000_000_007;
    int ALPHABET_SIZE = 26;

    public int makeStringSorted(String s) {
        int n = s.length();
        precomputeFactorials(n);

        int[] freq = new int[ALPHABET_SIZE];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        FenwickTree bit = new FenwickTree(ALPHABET_SIZE);
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            bit.update(i + 1, freq[i]);
        }

        long permsDenominatorInv = 1;
        for (int count : freq) {
            permsDenominatorInv = (permsDenominatorInv * power(fact[count], MOD - 2)) % MOD;
        }

        long totalOps = 0;
        for (int i = 0; i < n; i++) {
            int remainingChars = n - i;
            int charCode = s.charAt(i) - 'a';

            long countSmaller = bit.query(charCode);
            
            if (countSmaller > 0) {
                long term = (fact[remainingChars - 1] * countSmaller) % MOD;
                long contribution = (term * permsDenominatorInv) % MOD;
                totalOps = (totalOps + contribution) % MOD;
            }

            permsDenominatorInv = (permsDenominatorInv * freq[charCode]) % MOD;
            bit.update(charCode + 1, -1);
            freq[charCode]--;
        }

        return (int) totalOps;
    }

    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
    }

    private long power(long base, long exp) {
        long res = 1; base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD; exp /= 2;
        }
        return res;
    }

    class FenwickTree {
        int[] bit; int size;
        public FenwickTree(int size) { this.size = size; this.bit = new int[size + 1]; }
        public void update(int index, int delta) { while (index <= size) { bit[index] += delta; index += index & -index; } }
        public int query(int index) { int sum = 0; while (index > 0) { sum += bit[index]; index -= index & -index; } return sum; }
    }
}
```
### Algorithm
- `Precompute factorials up to n.`
- `Calculate initial character frequencies and initialize a Fenwick Tree with them.`
- `Calculate an initial denominator term: product of invFact[freq[c]] for all c.`
- `Initialize total_operations = 0.`
- `Iterate i from 0 to n-1:`
    - `Let m = n - i.`
    - `Use the Fenwick Tree to query the count of available characters smaller than s[i] in O(log A) time.`
    - `Calculate the contribution for this step using the precomputed factorials and the current denominator term.`
    - `Add the contribution to total_operations.`
    - `Update the denominator term for the next iteration in O(1) by multiplying by the current frequency of s[i].`
    - `Update the Fenwick Tree by decrementing the count of s[i] in O(log A) time.`
- `Return total_operations.`

# Solutions
### Java

```java
class Solution { private static final int N = 3010 ; private static final int MOD = ( int ) 1 e9 + 7 ; private static final long [] f = new long [ N ]; private static final long [] g = new long [ N ]; static { f [ 0 ] = 1 ; g [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; g [ i ] = qmi ( f [ i ], MOD - 2 ); } } public static long qmi ( long a , int k ) { long res = 1 ; while ( k != 0 ) { if (( k & 1 ) == 1 ) { res = res * a % MOD ; } k >>= 1 ; a = a * a % MOD ; } return res ; } public int makeStringSorted ( String s ) { int [] cnt = new int [ 26 ]; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } long ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int m = 0 ; for ( int j = s . charAt ( i ) - 'a' - 1 ; j >= 0 ; -- j ) { m += cnt [ j ]; } long t = m * f [ n - i - 1 ] % MOD ; for ( int v : cnt ) { t = t * g [ v ] % MOD ; } -- cnt [ s . charAt ( i ) - 'a' ]; ans = ( ans + t + MOD ) % MOD ; } return ( int ) ans ; } }
```

### CPP

```cpp
const int N = 3010 ; const int MOD = 1e9 + 7 ; long f [ N ]; long g [ N ]; long qmi ( long a , int k ) { long res = 1 ; while ( k != 0 ) { if (( k & 1 ) == 1 ) { res = res * a % MOD ; } k >>= 1 ; a = a * a % MOD ; } return res ; } int init = []() { f [ 0 ] = g [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; g [ i ] = qmi ( f [ i ], MOD - 2 ); } return 0 ; }(); class Solution { public: int makeStringSorted ( string s ) { int cnt [ 26 ]{}; for ( char & c : s ) { ++ cnt [ c - 'a' ]; } int n = s . size (); long ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int m = 0 ; for ( int j = s [ i ] - 'a' - 1 ; ~ j ; -- j ) { m += cnt [ j ]; } long t = m * f [ n - i - 1 ] % MOD ; for ( int & v : cnt ) { t = t * g [ v ] % MOD ; } ans = ( ans + t + MOD ) % MOD ; -- cnt [ s [ i ] - 'a' ]; } return ans ; } };
```

### Python

```python
n = 3010 mod = 10 ** 9 + 7 f = [ 1 ] + [ 0 ] * n g = [ 1 ] + [ 0 ] * n for i in range ( 1 , n ): f [ i ] = f [ i - 1 ] * i % mod g [ i ] = pow ( f [ i ], mod - 2 , mod ) class Solution : def makeStringSorted ( self , s : str ) -> int : cnt = Counter ( s ) ans , n = 0 , len ( s ) for i , c in enumerate ( s ): m = sum ( v for a , v in cnt . items () if a < c ) t = f [ n - i - 1 ] * m for v in cnt . values (): t = t * g [ v ] % mod ans = ( ans + t ) % mod cnt [ c ] -= 1 if cnt [ c ] == 0 : cnt . pop ( c ) return ans
```