【Python】文字列をソート済みにするまでの最小操作回数を求めるアルゴリズム

問題の概要

文字列 s が与えられます。この文字列に対して、昇順に並んだ「ソート済みの文字列」になるまで、以下の一連の操作を繰り返し適用します。

• ステップ1： 1 ≤ i < len(s) を満たし、かつ s[i] < s[i - 1] となる最大のインデックス i を選びます。
• ステップ2： i ≤ j < len(s) を満たし、範囲 [i, j] に含まれるすべての k について s[k] < s[i - 1] が成り立つ最大のインデックス j を選びます。
• ステップ3： インデックス i - 1 と j の位置にある2つの文字を入れ替えます。
• ステップ4： インデックス i 以降の接尾辞（サフィックス）を反転します。

文字列をソート済みの状態にするまでに必要な操作回数を求めてください。答えは非常に大きな値になる可能性があるため、結果は 10^9 + 7 で割った余りを返します。

具体例

例として、入力が s = "ppqpp" の場合を考えてみましょう。このとき出力は 2 になります。その過程を確認してみます。

• 1回目の操作： 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" となり、ソートが完了します。

解法のアプローチ

この問題は、文字列を右から左へ逆順に走査しながら、組み合わせ論的なカウント手法を用いることで効率的に解くことができます。手順は以下の通りです。

1. d := サイズ26の配列を用意し、すべての要素を0で初期化します（各アルファベットの出現数を記録するため）。
2. a := 0、t := 1 と初期化します。
3. m := 10^9 + 7（剰余演算に使用する値）とします。
4. n := 文字 'a' のASCIIコードとします。
5. 文字列 s を末尾から先頭に向かって走査します。インデックス i は1から始まり、各文字 c に対して以下の処理を行います。
   • j := ord(c) - n（文字 c のアルファベット上の位置を取得）
   • d[j] := d[j] + 1（その文字の出現数をカウントアップ）
   • a := (a + d[0]〜d[j-1] の総和 × t ÷ d[j]) mod m（ここで操作数を累積加算）
   • t := t × i ÷ d[j]（係数 t を更新）
6. ループ終了後、累積値 a を返します。

このアルゴリズムでは、ある時点で「現在注目している文字より小さい文字」がすでに何個出現しているかを記録することで、残りの操作回数を重複順列の考え方に基づいて一括算出できるのがポイントです。これにより、文字列長に対して線形時間 O(n) で答えを求めることができます。

Pythonでの実装例

理解を深めるために、実際のPythonコードを見てみましょう。

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

コードでは、s[::-1] によって文字列を逆順に取得し、enumerate の第2引数に1を指定することでインデックスを1から開始しています。各ステップで整数除算（//）を使うことで、正確な係数計算を実現しています。