3863.将一个字符串排序的最小操作次数

目标

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

在一次操作中，你可以选择 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 <= 10^5
• s 仅由小写英文字母组成。

思路

有一个字符串 s，每次操作可以将其子串（不能是整个字符串）按非递减排序，求使整个字符串按非递减排列所需的最小操作次数，如果无法实现返回 -1。

分类讨论：

• 如果 s 本身非递减，操作次数为 0。
• 否则，找出最大字符 max 与 最小字符 min：
  • 如果 s[0] == min || s[n - 1] == max，只需将剩余部分排序即可，操作次数为 1。
  • 如果 s[0] == max && s[n - 1] == min：
  • 如果字符串中有多余的 min 或者 max，可以直接排序前缀 s[0, n - 2] 或后缀 s[1, n - 1] 使得最大或最小归位，然后再排序剩余部分，操作次数为 2。
  • 否则，需要先将 min 与 max 移出来：
    • 如果 n == 2，返回 -1。
    • 否则，将 min 与 前一个的元素交换，排序前缀 s[0, n - 2]，然后再排序后缀 s[1, n - 1]，操作次数为 3。
  • 其余情况，先排序前缀 s[0, n - 2] 再排序后缀 s[1, n - 1] 即可，操作次数为 2。

代码

/**
 * @date 2026-10-21 9:10
 */
public class MinOperations3863 {

    public int minOperations(String s) {
        int max = s.charAt(0);
        int min = max;
        char[] chars = s.toCharArray();
        int[] cnt = new int[26];
        int n = chars.length;
        boolean ordered = true;
        for (char c : chars) {
            if (c < max) {
                ordered = false;
            }
            cnt[c - 'a']++;
            max = Math.max(max, c);
            min = Math.min(min, c);
        }
        if (ordered) {
            return 0;
        } else if (max == s.charAt(n - 1) || min == s.charAt(0)) {
            return 1;
        } else if (max == s.charAt(0) && min == s.charAt(n - 1)) {
            if (n == 2) {
                return -1;
            } else if (cnt[min - 'a'] > 1 || cnt[max - 'a'] > 1) {
                return 2;
            } else {
                return 3;
            }
        }
        return 2;
    }

}

性能