Pythonで解く：文字列sから削除してもtが部分列であり続ける最大の部分文字列の長さを求める方法

文字列 s と、s の部分列（サブシーケンス）となっている別の文字列 t が与えられます。求めたいのは、削除した後も t が s の部分列であり続けるような、削除可能な部分文字列の長さの最大値です。

たとえば、入力が s = "xyzxyxz"、t = "yz" の場合、出力は 4 になります。先頭の4文字 "xyzx" を削除しても、残った文字列には依然として "yz" が部分列として含まれているためです。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。ポイントは、次の3つの候補を調べることです。

• c1（末尾側の削除）：左から貪欲に t をマッチングさせ、最後の文字が一致した位置より後ろをすべて削除できる長さ。
• c2（先頭側の削除）：右から貪欲に t をマッチングさせ、最初の文字が一致した位置より前をすべて削除できる長さ。
• c3（中間の削除）：左寄せのマッチング位置と右寄せのマッチング位置の間にあるギャップのうち、最大のもの。

具体的な手順

1. 空のリスト left と right を用意し、c1 = c2 = c3 = -1、j = 0 で初期化します。
2. i を 0 から s の末尾まで順に走査します。s[i] が t[j] と一致したら、i を left の末尾に追加して j を1増やします。j が t の長さに達したら、c1 = len(s) - i - 1 としてループを抜けます。
3. 次に j = len(t) - 1 とし、i を s の末尾から先頭へ向かって走査します。s[i] が t[j] と一致したら、i を right の先頭に挿入して j を1減らします。j が -1 になったら、c2 = i としてループを抜けます。
4. i を 0 から len(t) - 2 まで走査し、c3 = max(c3, right[i + 1] - left[i] - 1) を計算します。
5. 最後に c1、c2、c3 の最大値を返します。

Pythonでの実装例

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

class Solution:
   def solve(self, s, t):
      left = []
      right = []
      c1 = -1
      c2 = -1
      c3 = -1
      j = 0
      for i in range(len(s)):
         if s[i] == t[j]:
            left.append(i)
            j += 1
         if j == len(t):
            c1 = len(s) - i - 1
            break
      j = len(t) - 1
      for i in range(len(s) - 1, -1, -1):
         if s[i] == t[j]:
            right.insert(0, i)
            j -= 1
         if j == -1:
            c2 = i
            break
      for i in range(len(t) - 1):
         c3 = max(c3, right[i + 1] - left[i] - 1)
      return max(c1, c2, c3)
ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

入力

"xyzxyxz", "yz"

出力

4

このアルゴリズムの計算量は O(n) であり、文字列を数回走査するだけで答えが求まるため、非常に効率的です。部分列のマッチング問題において、貪欲に左端・右端を固定して中間の余白を最大化するという発想は、他の文字列処理の問題にも応用できます。