Pythonで最長の回文部分列（パリンドローム）の長さを求めるプログラム

問題概要

小文字のみで構成された文字列 s が与えられます。この文字列から文字を順番を崩さずに選んで作れる、最長の回文部分列（パリンドロームサブシーケンス）の長さを求めましょう。

例えば、入力が s = "aolpeuvekyl" の場合、出力は 5 となります。これは、l・e・v・e・l を順に選ぶことで回文 "level" が構成できるためです。

解法のアプローチ

この問題は、区間を対象とした再帰的な動的計画法で解くことができます。区間 [i, j] における最長回文部分列の長さを dp(i, j) として定義し、以下の手順に従って計算します。

• n := 文字列 s のサイズとする
• 関数 dp() を定義する。引数は i と j
• i と j が等しい場合は 1 を返す（1文字は必ず回文になる）
• そうでなく i > j の場合は 0 を返す（空の区間のため）
• それ以外の場合は次のように処理する
  • s[i] と s[j] が等しい場合：両端の文字を回文に使えるので、2 + dp(i + 1, j - 1) を返す
  • 等しくない場合：どちらか一方の端を除外して比較するため、max(dp(i + 1, j), dp(i, j - 1)) を返す
• 最後に dp(0, n - 1) を返す

Pythonでの実装例

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

class Solution:
   def solve(self, s):
      n = len(s)
      def dp(i, j):
         if i == j:
            return 1
         elif i > j:
            return 0
         else:
            if s[i] == s[j]:
               return 2 + dp(i + 1, j - 1)
            else:
               return max(dp(i + 1, j), dp(i, j - 1))
      return dp(0, n - 1)
ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

入力

"aolpeuvekyl"

出力

5

計算量について

状態 (i, j) の組み合わせは最大で O(n²) 個存在します。各状態の計算は定数時間で行えるため、メモ化（キャッシュ）を追加すれば、全体の時間計算量は O(n²)、空間計算量も O(n²) に抑えられます。文字列が長くなる場合でも効率的に動作する実装となっています。