C++ में एक स्ट्रिंग पैलिंड्रोम बनाने के लिए विलोपन की न्यूनतम संख्या।

समस्या कथन

आकार 'एन' की एक स्ट्रिंग को देखते हुए। कार्य स्ट्रिंग पैलिंड्रोम बनाने के लिए वर्णों की न्यूनतम संख्या को हटाना है।

यदि दी गई स्ट्रिंग "abcda" है तो हम इसे पैलिंड्रोम बनाने के लिए पहले और अंतिम को छोड़कर किन्हीं भी 2 वर्णों को हटा सकते हैं।

• अगर हम अक्षर 'b' और 'c' को हटाते हैं तो "ada" स्ट्रिंग एक पैलिंड्रोम है

• अगर हम अक्षर 'c' और 'd' को हटा दें तो "aba" स्ट्रिंग एक पैलिंड्रोम है

• अगर हम अक्षर 'बी' और 'डी' हटाते हैं तो "एका" स्ट्रिंग एक पैलिंड्रोम है

एल्गोरिदम

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