Số lần xóa tối thiểu để tạo một chuỗi palindrome trong C ++.

Tuyên bố vấn đề

Cho một chuỗi có kích thước ‘n’. Nhiệm vụ là xóa một số ký tự tối thiểu để tạo chuỗi palindrome.

Nếu chuỗi đã cho là “abcda” thì chúng ta có thể xóa 2 ký tự bất kỳ trừ ký tự đầu tiên và ký tự cuối cùng để biến nó thành palindrome.

• Nếu chúng ta xóa ký tự ‘b’ và ‘c’ thì chuỗi “ada” là một palindrome

• Nếu chúng ta xóa ký tự ‘c’ và ‘d’ thì chuỗi “aba” là một palindrome

• Nếu chúng ta xóa ký tự ‘b’ và ‘d’ thì chuỗi “aca” là một palindrome

Thuật toán

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.

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum characters to be deleted = 2