)
这道题的本质是计算给定字符串 s 在其所有字符构成的全排列中，按字典序排在第几位（从0开始计数）。题目中描述的“交换并反转”操作，实际上就是生成当前排列的前一个字典序排列。因此，将字符串 s 变为升序所需的最少操作次数，就等于比 s 字典序小的排列总数。
我们可以使用组合数学中的方法来求解。基本思路是：从左到右遍历字符串 s 的每个位置 i，计算有多少个排列满足以下条件：
1. 前 i 个字符与 s 的前 i 个字符完全相同。
2. 第 i+1 个字符比 s[i] 小。
将所有这些情况的排列数累加起来，就是最终答案。
计算特定字符组合的排列数需要用到多重集的排列公式：P = n! / (c1! * c2! * ... * ck!)，其中 n 是总字符数，ci 是第 i 种字符的出现次数。
由于结果可能非常大，我们需要对 10^9 + 7 取模。这涉及到计算阶乘和阶乘的乘法逆元。
解题步骤
1. 预处理：预先计算好所有可能用到的阶乘值及其乘法逆元，以加速后续计算。
2. 统计频率：统计字符串 s 中每个字符的出现频率。
3. 遍历计算：遍历字符串 s 的每个位置 i：
* 对于所有比 s[i] 小的字符 ch，如果 ch 还有剩余（频率大于0），则尝试将 ch 放在位置 i。
* 将 ch 的频率减1，然后使用排列公式计算剩余字符能构成多少种排列。
* 将计算出的排列数加到结果中。
* 恢复 ch 的频率（回溯）。
* 最后，将 s[i] 的频率减1，因为我们已经固定了位置 i 的字符为 s[i]，继续处理下一个位置。
Java 代码实现
class Solution {
// 定义模数
private static final int MOD = 1000000007;
public int makeStringSorted(String s) {
int n = s.length();
// 1. 预处理阶乘和阶乘的逆元
// fact[i] 存储 i! % MOD
// invFact[i] 存储 (i!)⁻¹ % MOD
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i a⁻¹ ≡ a^(p-2) (mod p)
invFact[n] = quickPow(fact[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) {
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
// 2. 统计每个字符的频率
int[] charCount = new int[26];
for (char c : s.toCharArray()) {
charCount[c - 'a']++;
}
long result = 0;
// 3. 遍历字符串的每个位置
for (int i = 0; i 0) {
// 假设在位置 i 放置字符 smallerCharIndex
charCount[smallerCharIndex]--;
// 计算剩余 n - i - 1 个位置可以形成的排列数
// 排列数 = (剩余字符总数)! / (各字符频率的阶乘之积)
long permutations = fact[n - i - 1];
for (int count : charCount) {
permutations = (permutations * invFact[count]) % MOD;
}
// 将排列数累加到结果中
result = (result + permutations) % MOD;
// 回溯，恢复字符频率
charCount[smallerCharIndex]++;
}
}
// 固定当前位置的字符为 s[i]，继续处理下一个位置
charCount[currentCharIndex]--;
}
return (int) result;
}
// 快速幂算法，用于计算 (base^exp) % mod
private long quickPow(long base, long exp) {
long res = 1;
while (exp > 0) {
if ((exp & 1) == 1) {
res = (res * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
}
针对上述 Java 代码实现，以下是详细的时间和空间复杂度分析。
假设输入字符串 s 的长度为 N。
⏱️ 时间复杂度：O(N)
乍看之下，代码中有三层嵌套循环（遍历字符串、遍历26个字母、计算排列时遍历26个字母），似乎复杂度较高，但实际上由于常数项的存在，整体复杂度是线性的。
1. 预处理阶乘与逆元：
* 计算 fact 数组和 invFact 数组各需要遍历一次长度为 N 的数组。
* 耗时：O(N)。
2. 主循环逻辑：
* 外层循环：遍历字符串 s，共执行 N 次。
* 内层循环：遍历比当前字符小的字母（最多 26 个）。这是一个常数上限。
* 排列计算：在计算 permutations 时，需要遍历 charCount 数组（固定长度为 26）来累乘逆元。这也是一个常数操作。
* 综合计算：主循环部分的总操作次数约为 N times 26 times 26。由于 26 是常数，不随 N 增长，因此这部分的时间复杂度为 O(N)。
3. 快速幂：
* 仅在预处理阶段调用一次，用于计算 fact[N] 的逆元。其复杂度为 O(log MOD)，相对于 N 来说可以视为常数或忽略不计。
结论：综合以上步骤，总时间复杂度为 O(N) + O(N) = O(N)。
💾 空间复杂度：O(N)
空间消耗主要来自于预处理的数组和字符计数数组。
1. 预处理数组：
* 我们需要创建 fact 和 invFact 两个 long 类型数组，长度均为 N + 1。
* 占用空间：O(N)。
2. 字符计数数组：
* charCount 数组用于统计字母频率，长度固定为 26。
* 占用空间：O(1)。
3. 其他变量：
* 循环变量、临时变量等占用常数空间 O(1)。
结论：总空间复杂度由预处理数组主导，为 O(N)。
📊 复杂度总结表
复杂度类型 复杂度 说明
时间复杂度 O(N) 预处理 O(N) + 主逻辑 O(N times 26^2)，常数省略。
空间复杂度 O(N) 主要用于存储阶乘和逆元数组。
