Pythonで回文にするために必要な最小スワップの数をカウントするプログラム

文字列sがあるとすると、回文にするために必要な隣接スワップの最小数を見つける必要があります。そのような解決方法がない場合は、-1を返します。

したがって、入力がs ="xxyy"の場合、出力は2になります。これは、中央の"x"と"y"を入れ替えて、文字列が "xyxy"になり、最初の2つの"x"と"を入れ替えることができるためです。 y」で「yxxy」を取得します。これは回文です。

これを解決するには、次の手順に従います-

• 関数util（）を定義します。これには時間がかかります

• 見た：=新しい地図

• sの各iについて、実行します

  • sawed [i]：=1 +（存在する場合はseen [i]、それ以外の場合は0）

• odd_count：=0

• 表示されたキーと値のペアごとに、実行します

  • 値が奇数の場合、

    • odd_count：=odd_count + 1

  • odd_countが2と同じ場合、

    • Falseを返す

• Trueを返す

• メインの方法から、次のようにします-

• スワップ：=0

• util（s）がtrueの場合、

  • 左：=0

  • 右：=sのサイズ-1

  • s：=s

    から取得した新しい文字リスト

  • 左<右、する

    • s[左]がs[右]と同じでない場合、

      • k：=右

      • k>左で、s[k]はs[左]と同じではありませんが、実行してください

        • k：=k-1

      • kが左と同じ場合、

        • スワップ：=スワップ+ 1

        • s [左]、s [左+1]：=s[左+1]、s[左]

      • それ以外の場合

        • k <右、実行

          • スワップs[k]、s [k + 1]

          • k：=k + 1

          • スワップ：=スワップ+ 1

        • 左：=左+ 1

        • 右：=右-1

    • それ以外の場合

      • 左：=左+ 1

      • 右：=右-1

  • リターンスワップ

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

入力

"xxyy"

出力

2