समस्या विवरण
एक स्ट्रिंग दी गई है, स्ट्रिंग को पालिंड्रोम बनाने के लिए जोड़े जाने वाले न्यूनतम कैरेक्टर्स ढूंढें।
उदाहरण
यदि स्ट्रिंग 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
