日期：2026年10月21日
LeetCode 題目連結：3863. Minimum Operations to Sort a String
解題想法
中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 、只包含小寫英文字母的字串 $s$，如果每次操作可以取不是整個字串 $s$ 的任意長度子字串排序，至少要操作幾次才可以使 $s$ 依照字典序排序？如果無法排序，則回傳 $-1$。
分析這題可能的狀況及操作方式，可以分為以下 5 種狀況。
- 如果 $s$ 已經排序，不需要操作，回傳 $0$。
- 如果 $s$ 未排序且長度為 $2$，無法在不選取整個字串的狀況下排序，回傳 $-1$。
- 如果 $s$ 之中最小的字母 $mn$ 在 $s[0]$，或者最大的字母 $mx$ 在 $s[n-1]$，而且 $n \geq 3$，選取不包含位在 $s[0]$ 的 $mn$ 的子字串或是不包含位在 $s[n-1]$ 的 $mx$ 的子字串，只要操作 $1$ 次即可，回傳 $1$。
- 如果 $mn$ 在 $s[n-1]$，而且 $mx$ 在 $s[0]$，要先選擇包含 $mn$ 或 $mx$ 的子字串排序，將 $mn$ 放到 $s[0]$ 或是 $mx$ 放到 $s[n-1]$；再選取另一側的子字串，將另一個字母歸位；最後再處理中間的子字串，共操作 $3$ 次，回傳 $3$。
- 其它狀況，操作 $2$ 次，回傳 $2$。
Python 程式碼
Runtime: 240 ms, beats 34.85%. Memory: 19.85 MB, beats 90.91%.
class Solution:
def minOperations(self, s: str) -> int:
n = len(s) # 長度
# 檢驗 s 是否已排序，順便找最小字元 mn、最大字元 mx
is_sorted = True
pre, mn, mx = 'a', 'z', 'a'
mn_idx, mx_idx = -1, -1
for i in range(n):
c = s[i]
if c < pre:
is_sorted = False
pre = c
if c < mn: # mn 盡量靠前
mn = c
mn_idx = i
if c >= mx: # mx 盡量靠後
mx = c
mx_idx = i
# 特例，s 已排序，操作次數 0
if is_sorted: return 0
# 長度 2 且未排序，無法在不選取整個字串的狀況下完成排序，回傳 -1
if n == 2: return -1
# mn 在開頭或 mx 在結尾，n 大於、等於 3，操作 1 次
if (mn_idx == 0 or mx_idx == n - 1) and n >= 3: return 1
# 如果 mn 不在 s[0 : n-1]，即 mn 在 s[n-1]；且 mx 不在 s[1:]，即 mx 在 s[0]，操作 3 次
if mn_idx == n - 1 and mx_idx == 0: return 3
return 2
