给你一个字符串 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开始的字符串后缀反转。
请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 109 + 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" 。
示例 3：
输入：s = "cdbea" 输出：63
示例 4：
输入：s = "leetcodeleetcodeleetcode" 输出：982157772
提示：
1 <= s.length <= 3000s 只包含小写英文字母。
题目中的操作实际上是求当前排列的上一个字典序排列，因此，我们只需要求出比当前排列小的排列的数量，就是答案。
这里我们需要考虑一个问题，给定每一种字母的频率，我们可以构造出多少种不同的排列？
假设总共有
我们可以通过预处理的方式，预先计算出所有的阶乘
接下来，我们从左到右遍历字符串
遍历完整个字符串后，即可得到答案。注意答案的取模操作。
时间复杂度
n = 3010
mod = 10**9 + 7
f = [1] + [0] * n
g = [1] + [0] * n
for i in range(1, n):
f[i] = f[i - 1] * i % mod
g[i] = pow(f[i], mod - 2, mod)
class Solution:
def makeStringSorted(self, s: str) -> int:
cnt = Counter(s)
ans, n = 0, len(s)
for i, c in enumerate(s):
m = sum(v for a, v in cnt.items() if a < c)
t = f[n - i - 1] * m
for v in cnt.values():
t = t * g[v] % mod
ans = (ans + t) % mod
cnt[c] -= 1
if cnt[c] == 0:
cnt.pop(c)
return ansclass Solution {
private static final int N = 3010;
private static final int MOD = (int) 1e9 + 7;
private static final long[] f = new long[N];
private static final long[] g = new long[N];
static {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i % MOD;
g[i] = qmi(f[i], MOD - 2);
}
}
public static long qmi(long a, int k) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % MOD;
}
k >>= 1;
a = a * a % MOD;
}
return res;
}
public int makeStringSorted(String s) {
int[] cnt = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
++cnt[s.charAt(i) - 'a'];
}
long ans = 0;
for (int i = 0; i < n; ++i) {
int m = 0;
for (int j = s.charAt(i) - 'a' - 1; j >= 0; --j) {
m += cnt[j];
}
long t = m * f[n - i - 1] % MOD;
for (int v : cnt) {
t = t * g[v] % MOD;
}
--cnt[s.charAt(i) - 'a'];
ans = (ans + t + MOD) % MOD;
}
return (int) ans;
}
}const int N = 3010;
const int MOD = 1e9 + 7;
long f[N];
long g[N];
long qmi(long a, int k) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % MOD;
}
k >>= 1;
a = a * a % MOD;
}
return res;
}
int init = []() {
f[0] = g[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i % MOD;
g[i] = qmi(f[i], MOD - 2);
}
return 0;
}();
class Solution {
public:
int makeStringSorted(string s) {
int cnt[26]{};
for (char& c : s) {
++cnt[c - 'a'];
}
int n = s.size();
long ans = 0;
for (int i = 0; i < n; ++i) {
int m = 0;
for (int j = s[i] - 'a' - 1; ~j; --j) {
m += cnt[j];
}
long t = m * f[n - i - 1] % MOD;
for (int& v : cnt) {
t = t * g[v] % MOD;
}
ans = (ans + t + MOD) % MOD;
--cnt[s[i] - 'a'];
}
return ans;
}
};const n = 3010
const mod = 1e9 + 7
var f = make([]int, n)
var g = make([]int, n)
func qmi(a, k int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % mod
}
k >>= 1
a = a * a % mod
}
return res
}
func init() {
f[0], g[0] = 1, 1
for i := 1; i < n; i++ {
f[i] = f[i-1] * i % mod
g[i] = qmi(f[i], mod-2)
}
}
func makeStringSorted(s string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, c := range s {
m := 0
for j := int(c-'a') - 1; j >= 0; j-- {
m += cnt[j]
}
t := m * f[len(s)-i-1] % mod
for _, v := range cnt {
t = t * g[v] % mod
}
ans = (ans + t + mod) % mod
cnt[c-'a']--
}
return
}