题目描述

给你一个字符串 s （下标从 0 开始）。你需要对 s 执行以下操作直到它变为一个有序字符串：

• 找到 最大下标 i，使得 1 <= i < s.length 且 s[i] < s[i - 1]。
• 找到 最大下标 j，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i - 1]。
• 交换下标为 i - 1 和 j 处的两个字符。
• 将下标 i 开始的字符串后缀反转。

请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 10^9 + 7 取余 的结果。

样例

输入：s = "cba"
输出：5
解释：模拟过程如下所示：
操作 1：i=2，j=2。交换 s[1] 和 s[2] 得到 s="cab"，然后反转下标从 2 开始的后缀字符串，得到 s="cab"。
操作 2：i=1，j=2。交换 s[0] 和 s[2] 得到 s="bac"，然后反转下标从 1 开始的后缀字符串，得到 s="bca"。
操作 3：i=2，j=2。交换 s[1] 和 s[2] 得到 s="bac"，然后反转下标从 2 开始的后缀字符串，得到 s="bac"。
操作 4：i=1，j=1。交换 s[0] 和 s[1] 得到 s="abc"，然后反转下标从 1 开始的后缀字符串，得到 s="acb"。
操作 5：i=2，j=2。交换 s[1] 和 s[2] 得到 s="abc"，然后反转下标从 2 开始的后缀字符串，得到 s="abc"。

输入：s = "aabaa"
输出：2
解释：模拟过程如下所示：
操作 1：i=3，j=4。交换 s[2] 和 s[4] 得到 s="aaaab"，然后反转下标从 3 开始的后缀字符串，得到 s="aaaba"。
操作 2：i=4，j=4。交换 s[3] 和 s[4] 得到 s="aaaab"，然后反转下标从 4 开始的后缀字符串，得到 s="aaaab"。

输入：s = "cdbea"
输出：63

输入：s = "leetcodeleetcodeleetcode"
输出：982157772

限制

• 1 <= s.length <= 3000
• s 只包含小写英文字母。

算法

(数学) $O(n \log MOD)$

1. 结论：题目等价于求给定字符串在所有全排列中的排名。
2. 证明：每一次操作相当于将当前排列变为前一个排列（即排名更靠前的排列，排名第一的排列就是有序的字符串）。求上一个排列的精髓是尽可能在低位上，找到一个“小数”，与高位中的一个“大数”进行交换，然后做一些其他的操作，
   • 从后往前找到第一个 i 满足 s[i - 1] > s[i]，则 i 之后的数列必然是单调递增的，此时 s[i - 1] 就是一个“大数”。
   • 再按照题目所说，找到 j，此时 s[j] 就是“小数”。
   • 交换“大数”和“小数”，此时，i 的后缀一定是单调递增的，将其改为单调下降。
3. 得到了结论，接下来需要使用康拓展开，来求出当前排列的排名。
4. 假设数字无重复，则排名为 $X = A_0(n - 1)! + A_1(n - 2)! + \dots + A_{n - 1}0!$，其中 $A_i$ 为满足 $s(i) > s(j)$ 的 $j > i$ 的个数。简要说明，如果第一位为 $s_0$，但之后有 $A_0$ 个数字小于 $s_0$，则说明需要经过 $A_0(n - 1)!$ 这么多的数字，才能使 $s_0$ 站到最高位，依次类推。
5. 在有重复数字的情况下，每一次计算时，需要除以重复次数的阶乘乘积以去重。
6. 通过乘法逆元来计算除法。
7. 代码中为了方便，从 $n - 1$ 开始计算到 $0$，过程中累计计算乘积。求当前排名时，可以遍历频数数组来快速求解。

时间复杂度

• 对于每个位置，由于只有小写英文字母，所以仅需要常数的时间求排名，求逆元需要额外 $O(\log MOD)$ 的时间，故总时间复杂度为 $O(n \log MOD)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
private:
    LL power(LL x, LL y, LL mod) {
        LL tot = 1, p = x;
        for (; y; y >>= 1) {
            if (y & 1)
                tot = tot * p % mod;
            p = p * p % mod;
        }
        return tot;
    }

public:
    int makeStringSorted(string s) {
        const int n = s.size();
        const LL mod = 1000000007;

        LL fact = 1, dup = 1;
        LL res = 0;
        vector<int> seen(26, 0);
        for (int i = n - 1; i >= 0; i--) {
            seen[s[i] - 'a']++;
            dup = dup * seen[s[i] - 'a'] % mod;

            LL rk = 0;
            for (int j = 0; j < s[i] - 'a'; j++)
                rk += seen[j];

            res = (res + rk * fact % mod * power(dup, mod - 2, mod) % mod) % mod;
            fact = fact * (n - i) % mod;
        }

        return res;
    }
};