Minimum number of operations to make string sorted

Hash Table Math String Combinatorics Counting

50.7% acceptance

Feb 25, 2026

188

131

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_string_sorted(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = s.len();
    let bytes = s.as_bytes();

    // Precompute factorials and inverse factorials mod MOD
    let mut fact = vec![1i64; n + 1];
    for i in 1..=n { fact[i] = fact[i-1] * i as i64 % MOD; }
    let mut inv_fact = vec![1i64; n + 1];
    inv_fact[n] = Self::pow_mod(fact[n], MOD - 2, MOD);
    for i in (0..n).rev() { inv_fact[i] = inv_fact[i+1] * (i+1) as i64 % MOD; }

    // Count of each char in the full string
    let mut cnt = [0i32; 26];
    for &b in bytes { cnt[(b - b'a') as usize] += 1; }

    // prod_inv_fact = inverse of product of fact[cnt[c]] for all c
    let prod_inv = {
      let mut p = 1i64;
      for &c in &cnt { p = p * inv_fact[c as usize] % MOD; }
      p
    };

    let mut result = 0i64;
    let mut cur_prod_inv = prod_inv;

    for i in 0..n {
      let ci = (bytes[i] - b'a') as usize;
      // Count chars in remaining positions (i+1..n) that are < bytes[i]
      // They are in cnt[0..ci] (still including current position's impact)
      let count_less: i64 = cnt[..ci].iter().map(|&x| x as i64).sum();
      // contribution: count_less * (n-1-i)! * cur_prod_inv
      result = (result + count_less % MOD * fact[n - 1 - i] % MOD * cur_prod_inv) % MOD;

      // Update: remove s[i] from counts
      // cur_prod_inv currently = prod of inv_fact[cnt[c]] for all c
      // After removing s[i]: cnt[ci] decreases by 1
      // New prod_inv = old_prod_inv * fact[cnt[ci]] * inv_fact[cnt[ci]-1]
      //              = old_prod_inv * cnt[ci]  (since fact[k]*inv_fact[k-1] = k)
      cur_prod_inv = cur_prod_inv * cnt[ci] as i64 % MOD;
      cnt[ci] -= 1;
    }
    result as i32
  }

  fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
    let mut result = 1i64;
    base %= modulus;
    while exp > 0 {
      if exp & 1 == 1 { result = result * base % modulus; }
      base = base * base % modulus;
      exp >>= 1;
    }
    result
  }
}