Pythonで「すべてのxをyより前に配置する」ために必要な最小の反転回数を求めるプログラム

問題概要

小文字の文字列 s が与えられ、その文字は x と y のみで構成されているとします。ここで、「1つの x を y に変更する」、またはその逆の「1つの y を x に変更する」という操作を考えます。この操作を繰り返し行い、すべての x がすべての y よりも前に並ぶようにしたい場合、必要な操作の最小回数を求めるのが目的です。

たとえば、入力が s = "yxyyyyxyxx" の場合、出力は 4 になります。

解き方の手順

この問題は、以下の手順で解くことができます。

• y_left := 0 で初期化します。
• x_right := s 内の "x" の個数、res := s 内の "x" の個数 とします。
• s の各文字 item に対して、以下を繰り返します。
  • item が "x" の場合は、x_right を 1 減らします。
  • それ以外の場合は、y_left を 1 増やします。
  • res := min(res, y_left + x_right) として更新します。
• 最後に res を返します。

アルゴリズムの考え方

このアルゴリズムでは、文字列を左から右へ走査しながら、各位置を「区切り地点」として考えます。ある位置より左側にある y は x に変更する必要があり(これが y_left)、その位置以降にある x は y に変更する必要があります(これが x_right)。それぞれの区切り地点における変更回数の合計(y_left + x_right)を計算し、その最小値が答えとなります。

実装例

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

class Solution:
   def solve(self, s):
      y_left = 0
      x_right = res = s.count("x")
      for item in s:
         if item == "x":
            x_right -= 1
         else:
            y_left += 1
         res = min(res, y_left + x_right)
      return res
ob = Solution()
s = "yxyyyyxyxx"
print(ob.solve(s))

入力

"yxyyyyxyxx"

出力

4

計算量

このアルゴリズムの時間計算量は O(n)(n は文字列の長さ)であり、使用する変数が固定数であるため、空間計算量は O(1) です。文字列を一度だけ走査すればよいため、非常に効率的な解法といえます。