Pythonで文字列をソートするための最小操作数を見つけるプログラム

文字列sがあるとします。ソートされた文字列を取得するまで、sに対して次の操作を実行する必要があります-

• 1 <=i

• [i、j]の範囲内のすべての可能なkの値に対して、i <=j

• インデックスi-1とjで2文字を交換します。

• インデックスiのサフィックスを逆にします。

文字列をソートするために必要な操作の数を見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法とする結果を返します。

したがって、入力がs ="ppqpp"のような場合、出力は2になります。

• 最初の操作では、i =3、j=4です。 s[2]とs[4]を交換してs="ppppq"を取得し、インデックス3の部分文字列を逆にします。ここでs="pppqp"です。

• 2番目の操作では、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

• インデックスiとsの文字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]

    の商

• を返す

例

理解を深めるために、次の実装を見てみましょう

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))

入力

"ppqpp"

出力

2