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

难度: 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⁹ + 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 <= 3000
s 只包含小写英文字母。

Submission

运行时间: 192 ms

内存: 16.3 MB

class Solution:
    def makeStringSorted(self, s: str) -> int:
        counter, prod, res, mod = [0]*26, 1, 0, 1000000007
        for i, c in enumerate(s[::-1], 1):
            counter[ind:=ord(c)-97] += 1
            res, prod = (res+prod*sum(counter[:ind])//counter[ind])%mod, prod*i//counter[ind]
        return res

Explain

题解的核心思想是计算将字符串转化为有序状态的最小操作次数，这可以通过统计每个字符前有多少个字典顺序小于它的字符的全排列数来实现。具体实现是从字符串的尾部开始遍历，使用一个计数器数组来统计每个字符出现的次数，同时计算当前的全排列数。每次迭代中，我们计算将当前字符放在所有小于它的字符之前所需的操作数，并更新结果。此外，还需要维护一个累乘的变量来计算排列数，并考虑到重复字符对排列数的影响。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def makeStringSorted(self, s: str) -> int:
        counter, prod, res, mod = [0]*26, 1, 0, 1000000007 # 初始化计数器，排列数累积，结果和模数
        for i, c in enumerate(s[::-1], 1): # 从字符串尾部向前遍历
            counter[ind:=ord(c)-97] += 1 # 更新字符计数
            res, prod = (res+prod*sum(counter[:ind])//counter[ind])%mod, prod*i//counter[ind] # 计算当前字符产生的排列数并更新结果
        return res # 返回最终结果

Explore

在解题代码中，计数器数组是用来统计每个字符出现的次数。数组初始时为全0，长度为26，对应26个英文字母。代码中使用`counter[ind:=ord(c)-97] += 1`来更新计数器，其中`ind`是字符c对应的索引（通过ASCII码计算），而`c`是从字符串s的末尾开始遍历的当前字符。每次遍历到一个字符，就将该字符对应的计数器值增加1。

在计算全排列数时，考虑字符重复的影响是通过维护每个字符的出现频次并适当调整排列数计算公式来实现的。具体操作为，在计算可能的排列位置时，使用`prod*i//counter[ind]`来更新`prod`，其中`prod`代表当前的排列数累积，`i`是从1开始的迭代数，`counter[ind]`是当前字符的出现次数。这样的计算方法确保了在存在重复字符时，排列数是正确的，因为每增加一个重复字符，排列的可能性就会除以该字符的出现次数。

在提到的操作数的计算中，核心思想是利用当前字符能够插入到之前所有小于它的字符的位置数来计算。具体实现为`prod*sum(counter[:ind])//counter[ind]`。这里，`prod`是到当前为止的排列数累积，`sum(counter[:ind])`计算了所有小于当前字符（由`ind`索引指示）的字符的出现次数总和。这个总和表示在当前字符之前，有多少个位置可以被当前字符占据以形成一个新的排列。因此，乘以`prod`并除以当前字符的出现次数`counter[ind]`（为了每次考虑到重复字符的影响），就得到了将当前字符放在所有小于它的字符之前的操作数。