3863. Minimum Operations to Sort a String

Hyno

3 min read

·

Oct 21, 2026

--

Share

題目

You are given a string s consisting of lowercase English letters.

In one operation, you can select any substring of s that is not the entire string and sort it in non-descending alphabetical order.

Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.

思路

構了幾個 case 之後，注意到大部分 case 都可以在 2 次 sort 內解決，只要先排序 s[1…n-1] 再排序 s[2…n] 就好。

由於字串只有小寫英文字母，所以可以用 counting sort 快速排序。

如果陣列已經排序好，則回傳 0 。若沒排序好且字串長度小於 2 ，表示不可能排好，回傳 -1。

還有一種情況是只需要排序 s[1…n-1] 和 s[2…n] 就好，即開頭排序後不動、結尾排序後不動，這種回傳 1。

然後吃 WA，想了想有一種情況例外：s[0] 與 s[n] 單獨存在，且 s[0] 排序後會到最後面、s[n] 排序後會到最前面，這種情況會需要排序三次。

舉例來說 cba 就會需要 cba -> bca -> bac -> abc 這樣操作。
然而 cca 只需要 cca -> cac -> acc 就好。

把這個 case 判掉後就過了。

程式碼

• Runtime 11ms | Beats 73.01%
• Memory 29.22MB | Beats 45.13%

class Solution {
public:
    int minOperations(string s) {
        int n = s.size();

        bool sorted = true;
        char mn = 'z' + 1, mx = 'a' - 1;
        vector<int> cnt(256);
        for (int i = 0; i < n; i++) {
            mn = min(mn, s[i]);
            mx = max(mx, s[i]);
            if (i < n - 1 && s[i] > s[i + 1]) sorted = false;
            cnt[s[i]]++;
        }

        if (sorted) return 0;
        if (!sorted && n <= 2) return -1;

        if (s[0] == mn)
            return 1;
        if (s[n - 1] == mx)
            return 1;
        if (s[0] == mx && cnt[mx] == 1 && s[n - 1] == mn && cnt[mn] == 1)
            return 3;
        return 2;
    }
};