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

समस्या कथन

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

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

• यदि हम 'b' और 'c' हटाते हैं तो "ada" स्ट्रिंग पालिंड्रोम है
• यदि हम 'c' और 'd' हटाते हैं तो "aba" स्ट्रिंग पालिंड्रोम है
• यदि हम 'b' और 'd' हटाते हैं तो "aca" स्ट्रिंग पालिंड्रोम है

एल्गोरिदम

1. दी गई स्ट्रिंग का सबसे लंबा पालिंड्रोमिक सबसीक्वेंस ढूंढें। इसे "lpsSize" कहें।
2. हटाए जाने वाले न्यूनतम वर्ण = (स्ट्रिंग की लंबाई - lpsSize)

C++ उदाहरण

#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 - 1);
    return (n - lpsSize);
}

int main() {
    cout << "Minimum characters to be deleted = " << minDeletion("abcda") << endl;
    return 0;
}

आउटपुट

Minimum characters to be deleted = 2