C++で文字列を回文にするために必要な最小削除文字数を求める方法

問題の概要

長さ n の文字列が与えられたとき、その文字列を回文にするために削除が必要な最小の文字数を求めるのがこの問題の目的です。

たとえば、入力文字列が「abcda」の場合、先頭と末尾以外の2文字を削除すれば回文を作ることができます。

• 「b」と「c」を削除すると → 「ada」(回文になります)
• 「c」と「d」を削除すると → 「aba」(回文になります)
• 「b」と「d」を削除すると → 「aca」(回文になります)

アルゴリズムの考え方

この問題は「最長回文部分列(Longest Palindromic Subsequence: LPS)」の考え方を使うと効率的に解けます。手順は次のとおりです。

1. 与えられた文字列の中で最も長い回文部分列の長さを求めます(これを lpsSize とします)。
2. 削除が必要な最小文字数 = 文字列の長さ − lpsSize

つまり、「削除せずにそのまま残せる最大の回文」を見つければ、残りの文字がすべて削除対象になるというシンプルな発想です。

C++での実装例

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 区間 [i, j] における最長回文部分列の長さを再帰的に求める
int lps(const string& s, int i, int j){
    if (i == j) {
        return 1;  // 文字が1つだけならそれ自体が回文
    }
    if (s[i] == s[j] && i + 1 == j) {
        return 2;  // 隣接する2文字が一致する場合
    }
    if (s[i] == s[j]) {
        return lps(s, i + 1, j - 1) + 2;  // 両端が一致する場合
    }
    return max(lps(s, i, j - 1), lps(s, i + 1, j));  // どちらか一方を除外して比較
}

int minDeletion(const string& s){
    int n = s.size();
    int lpsSize = lps(s, 0, n - 1);  // 文字列全体を対象にする
    return n - lpsSize;
}

int main(){
    cout << "Minimum characters to be deleted = "
         << minDeletion("abcda") << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum characters to be deleted = 2

計算量と改善のヒント

上記の素朴な再帰実装は、同じ区間の計算が何度も繰り返されるため、最悪の場合には指数時間 O(2ⁿ) がかかる点に注意が必要です。

そこで実務では、メモ化(動的計画法)を組み合わせるのが一般的です。各区間 (i, j) の計算結果を表やキャッシュに保存することで、時間計算量を O(n²) まで抑えることができます。文字列が長くなるケースでは、必ずこの最適化を検討しましょう。