目标
给你一个由小写英文字母组成的字符串 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;
}
}
性能
