3863. Minimum Operations to Sort a String

2026, Oct 20 2 mins read

1. Description

Given a string s containing lowercase English letters, make its characters non-decreasing alphabetically.
Each operation chooses a nonempty contiguous substring shorter than s and rearranges that substring into alphabetical order.
Return the fewest operations needed, or -1 if no sequence of allowed operations can sort s.

2. Example

Example 1

Input: s = “dog”
Output: 1
Explanation: Rearranging “og” as “go” changes the string to “dgo”, so one operation suffices.

Example 2

Input: s = “card”
Output: 2
Explanation: First rearrange “car” as “acr” to obtain “acrd”. Then rearrange “rd” as “dr” to obtain the sorted string “acdr”.

Example 3

Input: s = “gf”
Output: -1
Explanation: Only single-character substrings may be selected, and sorting them cannot change the string.

3. Constraints

1 <= s.length <= 10$^5$
Every character of s is a lowercase English letter.

4. Solutions

Case Analysis

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 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 {
public:
    int minOperations(const string &str) {
        const int n = str.size();
        if (n == 1) {
            return 0;
        }

        char min_letter = str.front(), max_letter = str.front();
        bool is_sorted = true;
        for (int i = 1; i < n; ++i) {
            if (str[i] < str[i - 1]) {
                is_sorted = false;
            }

            min_letter = min(str[i], min_letter);
            max_letter = max(str[i], max_letter);
        }

        if (is_sorted) {
            return 0;
        }

        if (n == 2) {
            return -1;
        }

        if (min_letter == str.front() || max_letter == str.back()) {
            return 1;
        }

        for (int i = 1; i < n - 1; ++i) {
            if (str[i] == min_letter || str[i] == max_letter) {
                return 2;
            }
        }

        return 3;
    }
};

Search

Tags