Minimum Number of Operations to Make String Sorted
HardUpdated: Aug 2, 2025
Practice on:
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:
- Find the largest index
isuch that1 <= i < s.lengthands[i] < s[i - 1]. - Find the largest index
jsuch thati <= j < s.lengthands[k] < s[i - 1]for all the possible values ofkin the range[i, j]inclusive. - Swap the two characters at indices
i - 1 andj. - 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
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 <= 3000s 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
- Precompute factorials and modular inverses for up to n.
- For each position i, count how many characters less than s[i] appear after i.
- For each such character, add the number of permutations if s[i] is replaced by that character, using multinomial coefficients.
- Sum up for all positions.
Code
C++
#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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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()
}
}
Python
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
Rust
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
}
}
TypeScript
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.