C++で有効な回文（K-Palindrome）を判定する方法

問題の概要

文字列 s と整数 k が与えられたとき、その文字列が「K-回文（K-Palindrome）」であるかどうかを判定します。

K-回文とは、文字列から最大 k 文字を削除することで回文（前から読んでも後ろから読んでも同じ文字列）に変換できる文字列のことです。

例えば、入力が s = "abcdeca"、k = 2 の場合、「b」と「e」を削除すると「acdca」となり回文になるため、出力は true になります。

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

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

• 文字列 s と、それを逆順にした文字列との間でLCSを求める
• 回文にするために削除が必要な最小文字数は「sの長さ − LCS(s, 逆順のs)」で表される
• この値が k 以下であれば、その文字列はK-回文であると判定できる

これは、元の文字列と逆順の文字列に共通して現れる部分列が、そのまま回文として残せる文字列に対応するためです。

アルゴリズムの手順

LCSを求める関数 lcs()

1. 関数 lcs() を定義し、文字列 s と t を引数として受け取る
2. n := s のサイズとする
3. s と t の先頭に空白を1文字追加する（インデックスを1始まりに揃えるため）
4. (n+1) × (n+1) のサイズを持つ2次元配列 dp を定義する
5. i = 1 から n まで、j = 1 から n までの二重ループで以下を繰り返す：
   • dp[i][j] := max(dp[i-1][j], dp[i][j-1])
   • s[i] == t[j] の場合は、さらに dp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1]) を行う
6. dp[n][n] を返す

メイン処理 isValidPalindrome()

1. s が空文字列の場合は true を返す
2. s を逆順に並べた文字列 x を作成する
3. 「s.size() - lcs(s, x) <= k」の結果を返す

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lcs(string s, string t){
      int n = s.size();
      s = " " + s;
      t = " " + t;
      vector<vector<int> > dp(n + 1, vector<int>(n + 1));
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= n; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (s[i] == t[j])
            dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
         }
      }
      return dp[n][n];
   }
   bool isValidPalindrome(string s, int k) {
      if (!s.size())
      return true;
      string x = "";
      for (int i = s.size() - 1; i >= 0; i--)
         x += s[i];
      return s.size() - lcs(s, x) <= k;
   }
};
main(){
   Solution ob;
   cout << (ob.isValidPalindrome("abcdeca", 2));
}

入力

"abcdeca", 2

出力

1

出力が 1（true）となるのは、「abcdeca」から2文字以内の削除で回文を作れることを意味します。

計算量の目安

• 時間計算量： O(n²) — n は文字列の長さ。DPテーブル全体を埋めるためです。
• 空間計算量： O(n²) — 2次元DP配列を保持するためです。

なお、DP配列を1行ずつ更新するローリング配列のテクニックを使えば、空間計算量を O(n) まで削減することも可能です。