在C ++中构成字符串回文的最小删除数。

问题陈述

给定一个大小为'n'的字符串。任务是删除最少数量的字符以组成字符串回文。

如果给定的字符串是“ abcda”，那么我们可以删除除第2个字符外的任何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