在Python中找到使字符串排序所需的最小操作次数

假设我们有一个字符串s。我们必须对该字符串执行以下操作，直到我们得到一个排序的字符串−

选择最大的索引i（1 <= i < s的长度），使得s [i]
选择最大的索引j，使得i <= j < s的长度，并且对于范围[i，j]中的所有可能的k值，s [k]
交换索引i-1和j处的两个字符。
反转从索引i开始的后缀。

我们必须找到使字符串排序所需的操作次数。答案可能非常大，因此返回结果模10 ^ 9 + 7。

因此，如果输入类似于s =“ppqpp”，则输出将为2，因为

在第一次操作中，i = 3，j = 4。交换s [2]和s [4]以获得s =“ppppq”，然后反转索引3处的子字符串。现在，s =“pppqp”。
在第二次操作中，i = 4，j = 4。交换s [3]和s [4]以获得s =“ppppq”，然后反转索引4处的子字符串，现在，s =“ppppq”。

要解决此问题，我们将遵循以下步骤−

d：大小为26的数组，并填充为0
a：0，t：1
m：10 ^ 9 + 7
n：’a’的ASCII值
对于字符串s中的每个索引i和字符c，从1开始的索引，以相反的顺序执行以下操作
- j：字符c的ASCII值-n
- d [j]：d [j] + 1
- a：（a + d [从索引0到j-1的所有元素的总和] * t / d [j]的商）mod m
- t：t * i / d [j]的商
返回a

例

让我们看以下实现以获得更好的理解

def solve(s):
   d = [0]*26
   a = 0
   t = 1
   m = 10**9 + 7
   n = ord('a')
   for i,c in enumerate(s[::-1],1):
      j = ord(c) - n
      d[j] += 1
      a = (a+sum(d[:j])*t//d[j]) % m
      t = t*i//d[j]
   return a

s = "ppqpp"
print(solve(s))