Pythonで最長の偶数長回文部分列の長さを求めるプログラム（動的計画法）

文字列が与えられたとき、その中から「偶数の長さを持ち、中央以外では同じ文字が2つ連続して現れない」という条件を満たす回文部分列を見つけ、その長さを出力することを考えます。

たとえば、入力が s = 'efeffe' の場合、出力は 4 になります。これは、条件を満たす偶数長の回文部分列として「effe」（長さ4）のみが存在するためです。

解法のアプローチ

この問題は、動的計画法（DP）を用いて効率的に解くことができます。手順は以下のとおりです。

• n を文字列 s の長さとします。

• dp を n × n の二次元配列として初期化します。各要素は「(長さ, 文字)」というペアで、初期値は (0, '') です。

• i を n-1 から 0 まで減らしながらループします。

  • j を i+1 から n-1 まで増やしながらループします。

    • s[i] と s[j] が同じ文字で、かつ dp[i+1][j-1] に記録された文字が s[i] と異なる場合：

      • dp[i][j] を (dp[i+1][j-1][0] + 2, s[i]) に更新します。

    • それ以外の場合：

      • dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1] の中から、ペアの第1要素（長さ）が最大のものを選び、dp[i][j] に代入します。

• 最後に dp[0][n-1] の第1要素を返します。

アルゴリズムのポイント

このアルゴリズムの鍵は、DPテーブルに「長さ」だけでなく「内側の端の文字」も一緒に記録している点です。これにより、新しい文字ペアを追加する際に、既存の回文の端と同じ文字が隣接してしまうケース（＝中央以外で同一文字が連続する状態）を確実に回避できます。

実装例

def solve(s):
    n = len(s)
    dp = [[(0, '')]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
                dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
    return dp[0][n-1][0]
print(solve('efeffe'))

入力

'efeffe'

出力

4

計算量

時間計算量・空間計算量はいずれも O(n²) となります。文字列の長さに比例したサイズの二次元DPテーブルを使用するためです。