Minimum operations to sort a string

String

18.3% acceptance

Mar 17, 2026

You are given a string s consisting of lowercase English letters. In one operation, you can select any substring of s that is not the entire string and sort it in non-descending alphabetical order. Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();

    if n <= 1 {
      return 0;
    }

    // Check if already sorted
    let mut sorted = true;
    for i in 1..n {
      if bytes[i] < bytes[i - 1] {
        sorted = false;
        break;
      }
    }
    if sorted {
      return 0;
    }

    // n=2: only proper substrings are single chars (no-ops), impossible to sort.
    if n == 2 {
      return -1;
    }

    // For n >= 3, let target = sorted(s).
    // Let L = first mismatch index, R = last mismatch index vs target.
    //
    // 1 op: sort proper substring [l,r] containing [L,R]. Requires L>0 or R<n-1.
    //
    // If L=0 and R=n-1, 1 op is impossible (forced to sort entire string).
    // For 2 ops: after 1 proper sort, need the new mismatch to not span [0,n-1].
    //   Only sorts [0..n-2] (fixing left) or [1..n-1] (fixing right) can help:
    //   - Sort [0..n-2]: result[0] = min(s[0..n-2]) = target[0] iff global min NOT at s[n-1].
    //   - Sort [1..n-1]: result[n-1] = max(s[1..n-1]) = target[n-1] iff global max NOT at s[0].
    //
    // 3 ops needed iff global max is at s[0] AND global min is at s[n-1].
    // Otherwise 2 ops suffice. 3 ops always suffice (strategy: sort [1..n-1], [0..n-2], [1..n-1]).

    let mut target: Vec<u8> = bytes.to_vec();
    target.sort();

    let l = (0..n).find(|&i| bytes[i] != target[i]).unwrap();
    let r = (0..n).rev().find(|&i| bytes[i] != target[i]).unwrap();

    if l > 0 || r < n - 1 {
      return 1;
    }

    // L=0, R=n-1: can't fix in 1 op.
    // Strategy A: sort [0..n-2] first → after sort, L'>0 iff target[0] appears in s[0..n-2].
    // Strategy B: sort [1..n-1] first → after sort, R'<n-1 iff target[n-1] appears in s[1..n-1].
    // 3 ops needed only if both strategies fail:
    //   global min (target[0]) is exclusively at s[n-1], AND
    //   global max (target[n-1]) is exclusively at s[0].
    let min_char = target[0];
    let max_char = target[n - 1];
    let min_only_at_end = !bytes[..n - 1].contains(&min_char);
    let max_only_at_start = !bytes[1..].contains(&max_char);

    if min_only_at_end && max_only_at_start {
      3
    } else {
      2
    }
  }
}