HardRating 2620

1830. Minimum Number of Operations to Make String Sorted

hash-tablemathstringcombinatoricscounting

解題說明

Minimum Number of Operations to Make String Sorted

題目描述：給定一個字串 s，每次操作找到最大的索引 i 使得 s[i] < s[i-1]，然後找到最大的 j > i 使得 s[j] < s[i]，交換 s[i] 和 s[j]，再反轉 s[i+1:] 的部分。重複直到字串已排序。求操作次數。

解題思路：每次操作實際上是求「前一個排列」（previous permutation）。因此操作次數等於字串在所有排列中的排名減 1（排序後的字串排名為 0）。對於含重複字元的排列排名，從左到右對每個位置 i 計算：有多少個比 s[i] 小的字元可以放在位置 i，乘以剩餘位置的排列數（考慮重複），累加即為排名。使用階乘和逆階乘快速計算多重集排列數。

C++ 解法

複雜度分析

時間複雜度：O(n × 26) = O(n) — 遍歷每個位置，每次需 O(26) 計算較小字元數和逆階乘。

空間複雜度：O(n) — 階乘和逆階乘陣列。

虛擬碼

1. Precompute factorial and inverse factorial up to n
2. Count frequency of each character
3. For each position i from left to right:
   a. Count characters smaller than s[i] in remaining characters
   b. Compute multiset permutation count: smaller * (n-i-1)! / product(cnt[c]!)
   c. Add to answer (mod)
   d. Decrement cnt[s[i]]
4. Return answer

其他解法

直接模擬：每次執行 previous permutation 操作直到排序。時間為 O(排名 × n)，對於長字串完全不可行。

康托展開（Cantor expansion）：本解法即為廣義康托展開（處理重複元素）的應用。標準康托展開適用於無重複排列，本題需要額外除以各字元計數的階乘。

延伸思考

若操作改為求「下一個排列」直到逆序排列，答案有何變化？
若字串包含非字母字元（例如數字），排名計算是否有變化？
如何在不取模的情況下計算精確排名（大數運算）？

Minimum Number of Operations to Make String Sorted — CaffeCode