LeetCode 题解工作台
使字符串有序的最少操作次数
给你一个字符串 s （ 下标从 0 开始 ）。你需要对 s 执行以下操作直到它变为一个有序字符串： 找到 最大下标 i ，使得 1 且 s[i] 。 找到 最大下标 j ，使得 i 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] 。 交换下标为 i - 1 和 j …
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数学·string
答案摘要
题目中的操作实际上是求当前排列的上一个字典序排列，因此，我们只需要求出比当前排列小的排列的数量，就是答案。 这里我们需要考虑一个问题，给定每一种字母的频率，我们可以构造出多少种不同的排列？
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给你一个字符串 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 ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*26) due to iterating through the string and checking counts of smaller characters. Space complexity is O(n + 26) for factorials, inverses, and character counts. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect efficient combinatorial counting rather than naive simulation.
- question_mark
Watch for modulo arithmetic to prevent overflow with large n.
- question_mark
Clarify handling of repeated characters in the string.
常见陷阱
外企场景- error
Simulating every operation leads to timeouts for large strings.
- error
Ignoring repeated characters can give incorrect operation counts.
- error
Forgetting to apply modulo 10^9+7 results in overflow errors.
进阶变体
外企场景- arrow_right_alt
Calculate the minimum operations to sort a string using only swaps without reversals.
- arrow_right_alt
Determine the lexicographical rank of the string among all permutations.
- arrow_right_alt
Count operations when only adjacent swaps are allowed.