1830. 使字符串有序的最少操作次数

Hard

题目描述

给你一个字符串 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 取模的结果。

示例 1：

输入：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"。

示例 2：

输入：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"。

提示：

1 <= s.length <= 3000
s 仅由小写英文字母组成。

注意：

给定的操作实际上是获取字符串 s 的上一个排列
要解决这个问题，你需要分别处理每个后缀

解题思路

这道题的核心思路是理解题目描述的操作实际上是在求字符串的上一个排列。我们需要计算从当前字符串到字典序最小的排列（即有序字符串）需要多少次操作。

关键观察：

题目的操作过程实际上是标准的"下一个排列"算法的逆过程
我们可以从右到左处理每个位置，计算以该位置开始的后缀需要多少次操作
对于每个位置 i，我们需要计算有多少个排列在当前排列之前

算法思路：

从右到左遍历字符串，维护右侧字符的频次统计
对于位置 i，计算有多少个小于 s[i] 的字符在右侧，这些字符可以与 s[i] 交换
每次交换后，剩余的字符可以形成的排列数就是阶乘除以重复字符的阶乘
使用组合数学中的排列公式：n! / (n1! × n2! × … × nk!)，其中 n1, n2, …, nk 是各字符的重复次数

实现要点：

预计算阶乘和逆元，用于快速计算排列数
使用模运算处理大数
维护字符频次数组，动态更新排列数计算

代码实现

class Solution {
public:
    static const int MOD = 1e9 + 7;
    
    long long power(long long a, long long b, long long mod) {
        long long result = 1;
        while (b > 0) {
            if (b & 1) result = (result * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return result;
    }
    
    long long modInverse(long long a, long long mod) {
        return power(a, mod - 2, mod);
    }
    
    int makeStringSorted(string s) {
        int n = s.length();
        vector<long long> fact(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        
        vector<int> count(26, 0);
        long long result = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            count[s[i] - 'a']++;
            
            int smaller = 0;
            for (int j = 0; j < s[i] - 'a'; j++) {
                smaller += count[j];
            }
            
            if (smaller > 0) {
                long long permutations = fact[n - i - 1];
                for (int j = 0; j < 26; j++) {
                    if (count[j] > 0) {
                        permutations = (permutations * modInverse(fact[count[j]], MOD)) % MOD;
                    }
                }
                result = (result + (1LL * smaller * permutations) % MOD) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def makeStringSorted(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        
        # Precompute factorials
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        
        # Precompute modular inverses of factorials
        inv_fact = [1] * (n + 1)
        inv_fact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, 0, -1):
            inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD
        
        count = [0] * 26
        result = 0
        
        for i in range(n - 1, -1, -1):
            count[ord(s[i]) - ord('a')] += 1
            
            # Count characters smaller than s[i] on the right
            smaller = sum(count[j] for j in range(ord(s[i]) - ord('a')))
            
            if smaller > 0:
                # Calculate permutations of remaining characters
                permutations = fact[n - i - 1]
                for j in range(26):
                    if count[j] > 0:
                        permutations = (permutations * inv_fact[count[j]]) % MOD
                
                result = (result + smaller * permutations) % MOD
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private long Power(long a, long b, long mod) {
        long result = 1;
        while (b > 0) {
            if ((b & 1) == 1) result = (result * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return result;
    }
    
    private long ModInverse(long a, long mod) {
        return Power(a, mod - 2, mod);
    }
    
    public int MakeStringSorted(string s) {
        int n = s.Length;
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        
        int[] count = new int[26];
        long result = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            count[s[i] - 'a']++;
            
            int smaller = 0;
            for (int j = 0; j < s[i] - 'a'; j++) {
                smaller += count[j];
            }
            
            if (smaller > 0) {
                long permutations = fact[n - i - 1];
                for (int j = 0; j < 26; j++) {
                    if (count[j] > 0) {
                        permutations = (permutations * ModInverse(fact[count[j]], MOD)) % MOD;
                    }
                }
                result = (result + (long)smaller * permutations % MOD) % MOD;
            }
        }
        
        return (int)result;
    }
}

var makeStringSorted = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    
    function power(a, b, mod) {
        let result = 1n;
        a = BigInt(a);
        b = BigInt(b);
        mod = BigInt(mod);
        
        while (b > 0n) {
            if (b & 1n) result = (result * a) % mod;
            a = (a * a) % mod;
            b >>= 1n;
        }
        return Number(result);
    }
    
    function modInverse(a, mod) {
        return power(a, mod - 2, mod);
    }
    
    const fact = new Array(n + 1);
    fact[0] = 1;
    for (let i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    
    const count = new Array(26).fill(0);
    let result = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        count[s.charCodeAt(i) - 97]++;
        
        let smaller = 0;
        for (let j = 0; j < s.charCodeAt(i) - 97; j++) {
            smaller += count[j];
        }
        
        if (smaller > 0) {
            let permutations = fact[n - i - 1];
            for (let j = 0; j < 26; j++) {
                if (count[j] > 0) {
                    permutations = (permutations * modInverse(fact[count[j]], MOD)) % MOD;
                }
            }
            result = (result + (smaller * permutations) % MOD) % MOD;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n²)，其中 n 是字符串长度。对于每个位置需要计算排列数，涉及遍历字符频次数组
空间复杂度	O(n)，用于存储阶乘数组和字符频次数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析