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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
8
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

1
2
3
4
5
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.

Solution

Method 1 – Combinatorics (Count Lexicographically Smaller Permutations)

Intuition

The number of operations is the number of lexicographically smaller permutations of s. For each position, count how many smaller characters can be swapped forward, and use factorials to count permutations, adjusting for duplicates.

Approach

  1. Precompute factorials and modular inverses for up to n.
  2. For each position i, count how many characters less than s[i] appear after i.
  3. For each such character, add the number of permutations if s[i] is replaced by that character, using multinomial coefficients.
  4. Sum up for all positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MOD = 1e9+7;
vector<long long> fact, inv;
long long modpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD; b >>= 1;
    }
    return res;
}
void init(int n) {
    fact.assign(n+1, 1); inv.assign(n+1, 1);
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
    inv[n] = modpow(fact[n], MOD-2);
    for (int i = n-1; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
}
class Solution {
public:
    int makeStringSorted(string s) {
        int n = s.size(); init(n);
        vector<int> cnt(26, 0);
        for (char c : s) cnt[c-'a']++;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int ch = 0; ch < s[i]-'a'; ++ch) {
                if (cnt[ch] == 0) continue;
                cnt[ch]--;
                long long cur = fact[n-i-1];
                for (int x : cnt) cur = cur * inv[x] % MOD;
                ans = (ans + cur) % MOD;
                cnt[ch]++;
            }
            cnt[s[i]-'a']--;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func makeStringSorted(s string) int {
    MOD := int(1e9+7)
    n := len(s)
    fact := make([]int, n+1)
    inv := make([]int, n+1)
    fact[0] = 1
    for i := 1; i <= n; i++ { fact[i] = fact[i-1] * i % MOD }
    inv[n] = modpow(fact[n], MOD-2, MOD)
    for i := n-1; i >= 0; i-- { inv[i] = inv[i+1] * (i+1) % MOD }
    cnt := make([]int, 26)
    for _, c := range s { cnt[c-'a']++ }
    ans := 0
    for i := 0; i < n; i++ {
        for ch := 0; ch < int(s[i]-'a'); ch++ {
            if cnt[ch] == 0 { continue }
            cnt[ch]--
            cur := fact[n-i-1]
            for _, x := range cnt { cur = cur * inv[x] % MOD }
            ans = (ans + cur) % MOD
            cnt[ch]++
        }
        cnt[s[i]-'a']--
    }
    return ans
}
func modpow(a, b, mod int) int {
    res := 1
    for b > 0 {
        if b&1 == 1 { res = res * a % mod }
        a = a * a % mod; b >>= 1
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
class Solution {
    static final int MOD = 1000000007;
    static int[] fact, inv;
    static int modpow(int a, int b) {
        int res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = (int)((long)res * a % MOD);
            a = (int)((long)a * a % MOD); b >>= 1;
        }
        return res;
    }
    static void init(int n) {
        fact = new int[n+1]; inv = new int[n+1];
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = (int)((long)fact[i-1] * i % MOD);
        inv[n] = modpow(fact[n], MOD-2);
        for (int i = n-1; i >= 0; --i) inv[i] = (int)((long)inv[i+1] * (i+1) % MOD);
    }
    public int makeStringSorted(String s) {
        int n = s.length(); init(n);
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c-'a']++;
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int ch = 0; ch < s.charAt(i)-'a'; ++ch) {
                if (cnt[ch] == 0) continue;
                cnt[ch]--;
                long cur = fact[n-i-1];
                for (int x : cnt) cur = cur * inv[x] % MOD;
                ans = (ans + cur) % MOD;
                cnt[ch]++;
            }
            cnt[s.charAt(i)-'a']--;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    companion object {
        const val MOD = 1000000007
        lateinit var fact: IntArray
        lateinit var inv: IntArray
        fun modpow(a: Int, b: Int): Int {
            var res = 1L; var aa = a.toLong(); var bb = b
            while (bb > 0) {
                if (bb and 1 == 1) res = res * aa % MOD
                aa = aa * aa % MOD; bb = bb shr 1
            }
            return res.toInt()
        }
        fun init(n: Int) {
            fact = IntArray(n+1); inv = IntArray(n+1)
            fact[0] = 1
            for (i in 1..n) fact[i] = (fact[i-1].toLong() * i % MOD).toInt()
            inv[n] = modpow(fact[n], MOD-2)
            for (i in n-1 downTo 0) inv[i] = (inv[i+1].toLong() * (i+1) % MOD).toInt()
        }
    }
    fun makeStringSorted(s: String): Int {
        val n = s.length; init(n)
        val cnt = IntArray(26)
        for (c in s) cnt[c-'a']++
        var ans = 0L
        for (i in 0 until n) {
            for (ch in 0 until s[i]-'a') {
                if (cnt[ch] == 0) continue
                cnt[ch]--
                var cur = fact[n-i-1].toLong()
                for (x in cnt) cur = cur * inv[x] % MOD
                ans = (ans + cur) % MOD
                cnt[ch]++
            }
            cnt[s[i]-'a']--
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def makeStringSorted(self, s: str) -> int:
        MOD = 10**9+7
        from math import factorial
        n = len(s)
        fact = [1]*(n+1)
        for i in range(1, n+1): fact[i] = fact[i-1]*i % MOD
        inv = [1]*(n+1)
        inv[n] = pow(fact[n], MOD-2, MOD)
        for i in range(n-1, -1, -1): inv[i] = inv[i+1]*(i+1)%MOD
        cnt = [0]*26
        for c in s: cnt[ord(c)-97] += 1
        ans = 0
        for i in range(n):
            for ch in range(ord(s[i])-97):
                if cnt[ch] == 0: continue
                cnt[ch] -= 1
                cur = fact[n-i-1]
                for x in cnt: cur = cur*inv[x]%MOD
                ans = (ans + cur)%MOD
                cnt[ch] += 1
            cnt[ord(s[i])-97] -= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const MOD: i64 = 1_000_000_007;
fn modpow(mut a: i64, mut b: i64) -> i64 {
    let mut res = 1;
    while b > 0 {
        if b & 1 == 1 { res = res * a % MOD; }
        a = a * a % MOD; b >>= 1;
    }
    res
}
fn init(n: usize) -> (Vec<i64>, Vec<i64>) {
    let mut fact = vec![1; n+1];
    let mut inv = vec![1; n+1];
    for i in 1..=n { fact[i] = fact[i-1] * i as i64 % MOD; }
    inv[n] = modpow(fact[n], MOD-2);
    for i in (0..n).rev() { inv[i] = inv[i+1] * (i as i64 + 1) % MOD; }
    (fact, inv)
}
impl Solution {
    pub fn make_string_sorted(s: String) -> i32 {
        let n = s.len();
        let (fact, inv) = init(n);
        let mut cnt = vec![0; 26];
        for c in s.bytes() { cnt[(c - b'a') as usize] += 1; }
        let mut ans = 0i64;
        for (i, &c) in s.as_bytes().iter().enumerate() {
            for ch in 0..(c-b'a') {
                if cnt[ch as usize] == 0 { continue; }
                cnt[ch as usize] -= 1;
                let mut cur = fact[n-i-1];
                for &x in &cnt { cur = cur * inv[x as usize] % MOD; }
                ans = (ans + cur) % MOD;
                cnt[ch as usize] += 1;
            }
            cnt[(c-b'a') as usize] -= 1;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    makeStringSorted(s: string): number {
        const MOD = 1e9+7;
        const n = s.length;
        const fact = [1];
        for (let i = 1; i <= n; ++i) fact[i] = fact[i-1]*i%MOD;
        const inv = Array(n+1).fill(1);
        inv[n] = pow(fact[n], MOD-2, MOD);
        for (let i = n-1; i >= 0; --i) inv[i] = inv[i+1]*(i+1)%MOD;
        const cnt = Array(26).fill(0);
        for (const c of s) cnt[c.charCodeAt(0)-97]++;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            for (let ch = 0; ch < s.charCodeAt(i)-97; ++ch) {
                if (cnt[ch] == 0) continue;
                cnt[ch]--;
                let cur = fact[n-i-1];
                for (const x of cnt) cur = cur*inv[x]%MOD;
                ans = (ans + cur)%MOD;
                cnt[ch]++;
            }
            cnt[s.charCodeAt(i)-97]--;
        }
        return ans;
        function pow(a: number, b: number, mod: number): number {
            let res = 1;
            while (b > 0) {
                if (b & 1) res = res * a % mod;
                a = a * a % mod; b >>= 1;
            }
            return res;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n * 26) — n = length of s, for each position and character.
  • 🧺 Space complexity: O(n + 26) — for factorials and counts.