समस्या कथन
एक स्ट्रिंग को देखते हुए कार्य उस उप-स्ट्रिंग की अधिकतम लंबाई को खोजने के लिए है जिसे पालिंड्रोम में व्यवस्थित किया जा सकता है।
उदाहरण
यदि इनपुट स्ट्रिंग ="5432112356" तो उत्तर 6 है क्योंकि अधिकतम पैलिंड्रोम विकल्प "321123" है और इसकी लंबाई 6
हैएल्गोरिदम
- यदि उप-स्ट्रिंग की लंबाई विषम है, तो इसे अंतिम समाधान में नहीं माना जा सकता है।
- यदि उप-स्ट्रिंग की लंबाई सम है, तो यह एक संभावित समाधान तभी हो सकता है जब उस उप-स्ट्रिंग में प्रत्येक वर्ण सम संख्या में आता है जिसे डिक्शनरी काउंट का उपयोग करके किया जा सकता है। हम जाँचते हैं कि प्रत्येक वर्ण सम संख्या में आता है या नहीं। यदि हां, तो हम इसे संभावित समाधानों में से एक के रूप में शामिल करते हैं। फिर हम स्ट्रिंग में अगले वर्ण को शामिल करके अगला उप-स्ट्रिंग बनाते हैं जो कि केवल अंत में वृद्धि करके किया जा सकता है और पुनरावर्ती जांच कर सकता है कि क्या अधिक लंबाई वाली उप-स्ट्रिंग बनाई जा सकती है जो दी गई शर्तों को पूरा करती है और सभी संभव को अधिकतम लौटाती है समाधान
उदाहरण
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> countt;
bool isPalindromePossible(unordered_map<int, int> &countt) {
for (auto key : countt) {
if (key.second & 1) {
return false;
}
return true;
}
int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
if (end == str.length()) {
if ((end - start) % 2 == 0)
if (isPalindromePossible(countt))
return end - start;
return 0;
} else {
if ((end - start) % 2 == 0) {
if (isPalindromePossible(countt)) {
countt[str[end]]++;
return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
} else {
countt[str[end]]++;
return getMaxPalindrome(str, countt, start, end + 1);
}
} else {
countt[str[end]]++;
unordered_map<int, int>
c(countt.begin(), countt.end());
int length = getMaxPalindrome(str, c, start, end + 1);
countt[str[end]]--;
countt[str[start]]--;
return max(length, getMaxPalindrome(str, countt, start + 1, end));
}
}
}
int main(int argc, char const *argv[]) {
string str = "5432112356";
int start = 0, end = 0;
cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum palindrome length = 6