Q3. Minimum Operations to Sort a String

📘 題目敘述

給你只包含小寫字母的字串 s。每次操作可選任意非整串的子字串，並將其遞增排序。請求把 s 變成整體遞增排序所需最少操作次數，不可能則回傳 -1。

條件限制

• 1 <= s.length <= 10^5
• s 只由小寫英文字母組成

🧠 解題思路

先得到排序後目標字串 t，再以字首、字尾是否已在正確位置做分類判斷，直接推得最少操作次數。

所有變數

• t：排序後目標字串
• first/second：判斷頭尾交換型態
• fst/snd：字首、字尾是否已正確
• af/as：最小字元或最大字元是否重複

🪜 主要流程步驟

1. 先排序得到 t

若 s == t 直接回傳 0。

2. 判斷頭尾關係

根據 first/second/fst/snd 分類情況。

3. 處理 first && second

n == 2 回傳 -1，若有重複端點字元回傳 2，否則回傳 3。

4. 一般情況

fst || snd 回傳 1，否則回傳 2。

⏱️ 複雜度

• 時間複雜度：O(n log n)
• 空間複雜度：O(n)

💻 程式碼實作

class Solution {
public:
    int minOperations(string s) {
        string t = s;
        sort(t.begin(), t.end());
        if (s == t) {
            return 0;
        }
        bool first = false, second = false;
        bool af = false, as = false;
        bool fst = false, snd = false;
        int n = s.size();
        if (t[n - 1] == s[0]) {
            first = true;
        }
        if (t[0] == s[n - 1]) {
            second = true;
        }
        if (s[0] == t[0]) {
            fst = true;
        }
        if (s[n - 1] == t[n - 1]) {
            snd = true;
        }
        if (n >= 3 && t[0] == t[1]) {
            af = true;
        }
        if (n >= 3 && t[n - 1] == t[n - 2]) {
            as = true;
        }
        if (first && second) {
            if (n == 2) {
                return -1;
            } else if (af || as) {
                return 2;
            }
            return 3;
        }
        if (fst || snd) {
            return 1;
        }
        return 2;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-492/problems/minimum-operations-to-sort-a-string/