Pythonで文字列を回文にするために必要な最小スワップ回数を求めるプログラム

文字列 s が与えられたとき、隣接する文字を入れ替える操作（スワップ）を何回行えば回文にできるか、その最小回数を求める問題を考えます。どのように操作しても回文にできない場合は -1 を返します。

たとえば、入力が s = "xxyy" の場合、答えは 2 になります。まず中央付近の「x」と「y」を入れ替えて "xyxy" とし、続いて先頭の2文字「x」と「y」を入れ替えて "yxxy" にすれば、これは回文となるからです。

回文にできるかどうかの判定方法

文字列を回文にできる条件は、「奇数回出現する文字が高々1種類であること」です。この条件をチェックする補助関数 util() を、以下の手順で実装します。

• 関数 util(s) を定義し、引数として文字列 s を受け取ります。
• 辞書 seen を用意して、各文字の出現回数をカウントします。
• 出現回数が奇数になっている文字の個数を odd_count として記録します。
• odd_count が 2 になった時点で False を返します（回文にできません）。
• 最後まで問題がなければ True を返します。

最小スワップ数を求める手順

回文にできることが確認できたら、両端から中央へ向かって貪欲法（グリーディ法）でスワップ回数を数えていきます。

• swaps = 0 で初期化し、util(s) が True の場合のみ処理を進めます。
• ポインタ left = 0、right = len(s) - 1 を設定し、文字列をリストに変換します。
• left < right の間、以下を繰り返します。
  • s[left] と s[right] が一致していれば、left を +1、right を -1 して次へ進みます。
  • 一致しない場合は、k = right から左方向へ走査し、s[left] と同じ文字を探します。
  • k == left だった場合、その文字は中央に置くべき唯一の文字なので、s[left] と s[left + 1] を入れ替えて 1 スワップとしてカウントします。
  • それ以外の場合は、見つけた位置 k の文字を右端まで隣接スワップで移動させ、移動回数を swaps に加算します。その後 left を +1、right を -1 します。
• ループ終了後に swaps を返し、util(s) が False の場合は -1 を返します。

Pythonでの実装例

以下に実際の実装を示します。

class Solution:
   def solve(self, s):
      def util(s):
         seen = {}
         for i in s:
            seen[i] = seen.get(i, 0) + 1
         odd_count = 0
         for k, val in seen.items():
            if val & 1 == 1:
               odd_count += 1
            if odd_count == 2:
               return False
         return True
      swaps = 0
      if util(s):
         left = 0
         right = len(s) - 1
         s = list(s)
         while left < right:
            if s[left] != s[right]:
               k = right
               while k > left and s[k] != s[left]:
                  k -= 1
               if k == left:
                  swaps += 1
                  s[left], s[left + 1] = s[left + 1], s[left]
               else:
                  while k < right:
                     s[k], s[k + 1] = s[k + 1], s[k]
                     k += 1
                     swaps += 1
                  left += 1
                  right -= 1
            else:
               left += 1
               right -= 1
         return swaps
      return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))

計算量

最悪の場合、内側の走査で文字列全体を見る可能性があるため、時間計算量は O(n²)、文字列をリストにコピーするため空間計算量は O(n) となります。

入力

"xxyy"

出力

2