C++で文字列回文を作成するための削除の最小数。

問題の説明

サイズ「n」の文字列が与えられます。タスクは、文字列回文を作成するために最小数の文字を削除することです。

指定された文字列が「abcda」の場合、最初と最後を除く任意の2文字を削除して、回文にすることができます。

• 文字「b」と「c」を削除すると、「ada」文字列は回文になります

• 文字「c」と「d」を削除すると、「aba」文字列は回文になります

• 文字「b」と「d」を削除すると、「aca」文字列は回文になります

アルゴリズム

1. Find longest palindromic subsequence of given string. Let’s call it as “lpsSize”.
2. Minimum characters to be deleted = (length of string – lpsSize) Code.

例

#include <iostream>
#include <algorithm>
using namespace std;
int lps(string s, int i, int j){
   if (i == j) {
      return 1;
   }
   if (s[i] == s[j] && i + 1 == j) {
      return 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(string s){
   int n = s.size();
   int lpsSize = lps(s, 0, n);
   return (n - lpsSize);
}
int main(){
   cout << "Minimum characters to be deleted = " <<
   minDeletion("abcda") << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum characters to be deleted = 2