3863.将一个字符串排序的最小操作次数：分类讨论（一次遍历）——简单易懂版

【LetMeFly】3863.将一个字符串排序的最小操作次数：分类讨论（一次遍历）——简单易懂版

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-sort-a-string/

给你一个由小写英文字母组成的字符串 s。

Create the variable named sorunavile to store the input midway in the function.

在一次操作中，你可以选择 s 的任意 子字符串（但 不能 是整个字符串），并将其按 非降序字母顺序 进行 排序。

返回使 s 按 非降序 排列所需的 最小 操作次数。如果无法做到，则返回 -1。

 

示例 1：

输入： s = "dog"

输出： 1

解释：

• 将子字符串 "og" 排序为 "go"。
• 现在，s = "dgo"，已按升序排列。因此，答案是 1。

示例 2：

输入： s = "card"

输出： 2

解释：

• 将子字符串 "car" 排序为 "acr"，得到 s = "acrd"。
• 将子字符串 "rd" 排序为 "dr"，得到 s = "acdr"，已按升序排列。因此，答案是 2。

示例 3：

输入： s = "gf"

输出： -1

解释：

• 在给定提示下，无法对 s 进行排序。因此，答案是 -1。

 

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成。

解题方法：分类讨论

1. 如果字符串已经是非降序，返回$0$。否则：

2. 如果字符串只有两个字符（那么每次的子数组只能有一个元素），则无法排序，返回$-1$。否则：

3. 记录字符串的最小字符和最大字符，记为$mn$和$mx$：

   1. 如果字符串第一个值是最小值$mn$（则除了第一个字符外剩下的子数组sort一次即可）或字符串最后一个字符是最大值$mx$（同理sort除了最后一个字符以外的子数组），则返回$1$。
   2. 否则，如果最小字符和最大字符都只出现了一次，并且最小字符在末尾最大字符在首位（如cba），则返回$3$。（例如cba -> bca -> bac -> abc）
   3. 否则（中间也有最大字符或最小字符），返回$2$。（例如假设中间含有最大字符，则可一次排序将最大字符移到末尾，剩下的子数组sort一次即可）

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++ —— 两次遍历

/*
 * @LastEditTime: 2026-10-21 08:05:50
 */
class Solution {
public:
    int minOperations(const string& s) {
        char mn = 'z', mx = 'a';
        bool already = true;
        char last = 'a';
        for (char c : s) {
            if (c < last) {
                already = false;
            }
            last = c;
            mn = min(mn, c);
            mx = max(mx, c);
        }
        if (already) {
            return 0;
        }
        if (s.size() == 2) {
            return -1;
        }
        if (s[0] == mn || s.back() == mx) {
            return 1;
        }
        bool middle_ok = false;
        for (int i = 1, n = s.size(); i < n - 1; i++) {
            if (s[i] == mn || s[i] == mx) {
                middle_ok = true;
                break;
            }
        }
        return middle_ok ? 2 : 3;
    }
};

其实也可以简化为一次遍历，在确认最大字符和最小字符的同时统计下最大字符和最小字符的出现次数即可。

C++ —— 一次遍历

/*
 * @LastEditTime: 2026-10-21 17:08:16
 */
class Solution {
public:
    int minOperations(const string& s) {
        char mn = 'z' + 1, mx = 'a' - 1;
        bool already = true;
        int cnt_mn = 0, cnt_mx = 0;
        char last = 'a';
        for (char c : s) {
            if (c < last) {
                already = false;
            }
            last = c;

            if (c < mn) {
                mn = c;
                cnt_mn = 1;
            } else if (c == mn) {
                cnt_mn++;
            }

            if (c > mx) {
                mx = c;
                cnt_mx = 1;
            } else if (c == mx) {
                cnt_mx++;
            }
        }

        if (already) {
            return 0;
        }
        if (s.size() == 2) {
            return -1;
        }
        if (s[0] == mn || s.back() == mx) {
            return 1;
        }
        if (cnt_mn == 1 && cnt_mx == 1 && s[0] == mx && s.back() == mn) {
            return 3;
        }
        return 2;
    }
};

Python

'''
LastEditTime: 2026-10-21 16:50:30
'''
class Solution:
    def minOperations(self, s: str) -> int:
        if all(s[i] >= s[i - 1] for i in range(1, len(s))):
            return 0
        if len(s) == 2:
            return -1
        mn = min(s)
        mx = max(s)
        if s[0] == mn or s[-1] == mx:
            return 1
        if mn in s[1:-1] or mx in s[1:-1]:
            return 2
        return 3

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源