##### Welcome to Subscribe On Youtube

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

# 1830. Minimum Number of Operations to Make String Sorted

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:

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.

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

############

class Solution {
private static final int N = 3010;
private static final int MOD = (int) 1e9 + 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;
}
}

• // OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// Time: O(NM * log(MOD))
// Space: O(N)
class Solution {
long modpow(long base, long exp, long mod) {
long ans = 1;
while (exp) {
if (exp & 1) ans = (ans * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return ans;
}
public:
int makeStringSorted(string s) {
long N = s.size(), cnt[26] = {}, mod = 1e9 + 7, ans = 0;
vector<long> fact(N + 1, 1);
for (int i = 1; i <= N; ++i) fact[i] = (fact[i - 1] * i) % mod;
for (int i = N - 1; i >= 0; --i) {
++cnt[s[i] - 'a'];
long less = 0, div = 1;
for (int j = 0; j < 26; ++j) {
if (j < s[i] - 'a') less += cnt[j];
div = (div * fact[cnt[j]]) % mod;
}
ans = (ans + less * fact[N - i - 1] % mod * modpow(div, mod - 2, mod) % mod) % mod;
}
return ans;
}
};

• 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


• const n = 3010
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)

func qmi(a, k int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % mod
}
k >>= 1
a = a * a % mod
}
return res
}

func init() {
f[0], g[0] = 1, 1
for i := 1; i < n; i++ {
f[i] = f[i-1] * i % mod
g[i] = qmi(f[i], mod-2)
}
}

func makeStringSorted(s string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, c := range s {
m := 0
for j := int(c-'a') - 1; j >= 0; j-- {
m += cnt[j]
}
t := m * f[len(s)-i-1] % mod
for _, v := range cnt {
t = t * g[v] % mod
}
ans = (ans + t + mod) % mod
cnt[c-'a']--
}
return
}