Pythonで先頭・末尾の文字を削除して再挿入し、目標の文字列を作る最小操作回数を求める

問題概要

互いにアナグラム（同じ文字で構成される順列）の関係にある2つの文字列 S と T が与えられます。
S に対して許されている操作は、「先頭または末尾の1文字を取り除き、文字列中の任意の位置に挿入する」というものです。
この操作を繰り返して S を T に一致させるとき、必要となる最小の操作回数を求めます。

入出力の例

たとえば、入力が s = "zyvxw"、t = "vwxyz" の場合、出力は 3 になります。
実際の操作手順は次のとおりです。

• 末尾の "w" を取り除き、"v" の直後に挿入 → "zyvwx"
• 先頭の "z" を取り除き、"x" の直後に挿入 → "yvwxz"
• 先頭の "y" を取り除き、"x" の直後に挿入 → "vwxyz"

わずか3回の操作で S を T へ変換できました。

解法のアプローチ

この問題を解く鍵は、「移動しなくて済む文字をできるだけ多く残す」ことです。
S の連続した区間のうち、T の部分列としても一致する最長の区間を見つけられれば、その区間の文字はそのまま残せます。したがって、答えは「文字列の長さ n − 残せる最大区間の長さ」となります。

具体的には、次の手順で求めます。

• ans := s の長さ、n := s の長さ として初期化する
• i を 0 から n−1 まで動かし、残す区間の開始位置とする
• k := 0 とし、j を i から n−1 まで動かして区間の終端を伸ばしていく
• t を k 番目以降から走査し、s[j] と一致する文字が見つかれば、区間 [i, j] は T の部分列として成立しているため、ans を min(ans, n − (j − i + 1)) で更新する
• すべての開始位置について確認が終わったら、ans を返す

実装例（Python）

以下のコードで、より理解が深まります。

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

入力

"zyvxw", "vwxyz"

出力

3

計算量の目安

時間計算量：O(n² × m)（n は s の長さ、m は t の長さ）
空間計算量：O(1)