Pythonで最大k文字の削除により回文を作れるかどうかを判定するプログラム

文字列 s が与えられたとき、最大 k 文字を削除することでその文字列を回文（前から読んでも後ろから読んでも同じになる文字列）にできるかどうかを判定する問題を考えてみましょう。

例えば、s = "lieuvrel"、k = 4 という入力の場合、出力は True になります。3 文字を削除すれば回文 "level" を作ることができるためです。

解法のアプローチ：最長共通部分列（LCS）を活用する

この問題は、最長共通部分列（LCS：Longest Common Subsequence）を利用すると効率的に解けます。考え方のポイントは以下の通りです。

• 文字列 s と、それを逆順にした文字列との最長共通部分列の長さを求めます。
• 「元の文字列の長さ − LCS の長さ」が、回文にするために削除が必要な最小文字数に相当します。
• この値が k 以下であれば、最大 k 文字の削除で回文を作ることができます。

アルゴリズムの手順

まず、2 つの文字列 a, b を受け取る関数 lcs() を次のように定義します。

1. m := a の長さ、n := b の長さとする
2. (m + 1) × (n + 1) のサイズの表 table を用意し、すべて 0 で初期化する
3. i を 1 から m まで繰り返しながら、j を 1 から n まで繰り返す：
   　・a[i - 1] と b[j - 1] が一致する場合：table[i][j] := 1 + table[i - 1][j - 1]
   　・一致しない場合：table[i][j] := max(table[i][j - 1], table[i - 1][j])
4. table[m][n] を返す

メイン処理では、「len(s) − lcs(s, s の逆順) ≤ k」が成り立てば True を、そうでなければ False を返します。

実装例

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

class Solution:
    def solve(self, s, k):
        def lcs(a, b):
            m, n = len(a), len(b)
            table = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if a[i - 1] == b[j - 1]:
                        table[i][j] = 1 + table[i - 1][j - 1]
                    else:
                        table[i][j] = max(table[i][j - 1], table[i - 1][j])
            return table[m][n]

        return len(s) - lcs(s, s[::-1]) <= k
    
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

入力

"lieuvrel", 4

出力

True

計算量について

このアルゴリズムの時間計算量は O(m × n)、空間計算量も O(m × n) です（m, n はそれぞれ文字列の長さ）。動的計画法によって各部分問題を一度だけ計算するため、全ての削除パターンを総当たりする方法よりも大幅に効率的になっています。