Pythonで文字列tを別の文字列sの部分文字列にするために必要な最小操作回数を求めるプログラム

問題の概要

2つの文字列 s と t が与えられたとき、t を s の部分文字列にするために必要な最小の操作回数を求めます。ここでいう1回の操作とは、「s 内の任意の位置を選び、その位置の文字を任意の別の文字に変更する」ことを指します。

例えば、入力が s = "abbpqr"、t = "bbxy" の場合、出力は 2 になります。これは、s の部分文字列 "bbpq" に着目し、'p' を 'x' に、'q' を 'y' に変更することで t = "bbxy" と一致させられるためです。

解法のアプローチ

この問題はスライディングウィンドウ（全開始位置の走査）を使うことで簡単に解けます。s の中で長さ k（= t の長さ）に等しいすべての部分文字列を順番に取り出し、それぞれが t と何文字異なるかを数えます。その差分の最小値が答えになります。

• k := t の長さ、n := s の長さ とする
• ans := 10^10（十分に大きい初期値）
• i を 0 から n − k まで繰り返す：
  • ss := s[i] から s[i+k−1] までの部分文字列
  • ans := ans と「ss と t で一致しない文字の個数」のうち小さい方
• 最後に ans を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution:
   def solve(self, s, t):
      k, n = len(t), len(s)
      ans = 10**10
      for i in range(n - k + 1):
         ss = s[i:i+k]
         ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
      return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy"))

入力

"abbpqr", "bbxy"

出力

2

計算量について

このアルゴリズムでは、開始位置の候補は最大 n − k + 1 個あり、各候補ごとに長さ k の文字比較を行うため、時間計算量は O(n × k) となります。一方、追加のデータ構造が必要ないため、空間計算量は O(1)（部分文字列の生成を除く）で済みます。文字列の長さがそこまで大きくなければ、このシンプルな手法で十分に高速に動作します。