1830：使字符串有序的最少操作次数（2620 分）

2021-04-17 约 1001 字预计阅读 2 分钟次阅读

力扣第 50 场双周赛第 4 题

题目

给你一个字符串 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 只包含小写英文字母。

分析

#1 统计排列

这个过程实际上是变为 s 的上一个排列，因此统计比 s 小的排列个数即可
遍历每位 i，统计 s[:i] 不变，s[i] 变小的全排列，再除去重复排列即可
除法取模需要用到逆元

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


mod = 10**9+7
N = 3001
fac,inv = [1]*N,[1]*N
for i in range(2,N):
    fac[i] = fac[i-1]*i%mod
    inv[i] = pow(fac[i],-1,mod)
    
class Solution:
    def makeStringSorted(self, s: str) -> int:
        n = len(s)
        A = [ord(c)-ord('a')+1 for c in s]
        res = 0
        ct = [0]*27
        for a in A:
            ct[a] += 1
        for i,a in enumerate(A):
            t = fac[n-1-i]*sum(ct[b] for b in range(a))
            for c in range(1,27):
                t = t*inv[ct[c]]%mod
            res += t
            res %= mod
            ct[a] -= 1
        return res

219 ms

#2 增量优化

注意到遍历时，26 个 inv[ct[c]] 只有一项改变了，可以递推维护
比 a 小的数量可以用树状数组维护

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


mod = 10**9+7
N = 3001
fac,inv = [1]*N,[1]*N
for i in range(2,N):
    fac[i] = fac[i-1]*i%mod
    inv[i] = pow(fac[i],-1,mod)

class BIT:
    def __init__(self, n):
        self.n = n
        self.t = [0]*n

    def update(self, i, x):
        while i<self.n:
            self.t[i] += x
            i += i&-i

    def get(self, i):
        res = 0
        while i:
            res += self.t[i]
            i &= i-1
        return res

class Solution:
    def makeStringSorted(self, s: str) -> int:
        n = len(s)
        A = [ord(c)-ord('a')+1 for c in s]
        ct = [0]*27
        for a in A:
            ct[a] += 1
        t = 1
        bit = BIT(27)
        for a in range(1,27):
            t = t*inv[ct[a]]%mod
            bit.update(a,ct[a])
        res = 0
        for i,a in enumerate(A):
            res += t*fac[n-1-i]*bit.get(a-1)
            res %= mod
            ct[a] -= 1
            t = t*fac[ct[a]+1]*inv[ct[a]]%mod
            bit.update(a,-1)
        return res

63 ms

目录

1830：使字符串有序的最少操作次数（2620 分）

题目

分析

#1 统计排列

#2 增量优化

解答