समस्या कथन
एक स्ट्रिंग को देखते हुए, स्ट्रिंग पैलिंड्रोम बनाने के लिए जोड़े जाने वाले न्यूनतम वर्ण खोजें।
उदाहरण
यदि स्ट्रिंग abcac है तो हम 2 हाइलाइट किए गए वर्णों यानी abcacba को जोड़कर स्ट्रिंग पैलिंड्रोम बना सकते हैं
एल्गोरिदम
- जांचें कि क्या स्ट्रिंग पहले से ही पैलिंड्रोम है, यदि हाँ तो कोई वर्ण जोड़ने की आवश्यकता नहीं है।
- एक-एक करके एक वर्ण को स्ट्रिंग से हटा दें और जांचें कि शेष स्ट्रिंग पैलिंड्रोम है या नहीं
- उपरोक्त प्रक्रिया को तब तक दोहराएं जब तक कि स्ट्रिंग पैलिड्रोम न बन जाए
- अंतिम उत्तर के रूप में अब तक हटाए गए वर्णों की संख्या लौटाएं
उदाहरण
#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
int n = strlen(str);
if (n == 1) {
return true;
}
int start = 0, end = n - 1;
while (start < end) {
if (str[start] != str[end]) {
return false;
}
++start;
--end;
}
return true;
}
int requiredAppends(char *str) {
if (isPalindrome(str)) {
return 0;
}
return 1 + requiredAppends(str + 1);
}
int main() {
char *str = "abcac";
cout << "Characters to be appended = " << requiredAppends(str) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Characters to be appended = 2