C++ में अधिकतम सम लंबाई सब-स्ट्रिंग जो पैलिंड्रोम का क्रमपरिवर्तन है

समस्या कथन

एक स्ट्रिंग दी गई है, कार्य उस सब-स्ट्रिंग की अधिकतम लंबाई ढूंढना है जिसे पैलिंड्रोम में व्यवस्थित किया जा सकता है।

उदाहरण

यदि इनपुट स्ट्रिंग = "5432112356" है तो उत्तर 6 है क्योंकि अधिकतम पैलिंड्रोम सबस्ट्रिंग "321123" है और इसकी लंबाई 6 है

एल्गोरिदम

• यदि सब-स्ट्रिंग की लंबाई विषम है, तो इसे अंतिम समाधान में नहीं माना जा सकता।
• यदि सब-स्ट्रिंग की लंबाई सम है, तो यह तभी संभावित समाधान हो सकता है जब उस सब-स्ट्रिंग में प्रत्येक वर्ण सम संख्या में बार आता है जिसे डिक्शनरी काउंट का उपयोग करके किया जा सकता है। हम जांचते हैं कि प्रत्येक वर्ण सम संख्या में आता है या नहीं। यदि हां, तो हम इसे संभावित समाधानों में से एक के रूप में शामिल करते हैं। फिर हम स्ट्रिंग में अगले वर्ण को शामिल करके अगला सब-स्ट्रिंग बनाते हैं जिसे केवल एंड बढ़ाकर किया जा सकता है और रिकर्सिवली जांचते हैं कि क्या दी गई शर्तों को पूरा करने वाली अधिक लंबाई की सब-स्ट्रिंग बनाई जा सकती है और सभी संभावित समाधानों का अधिकतम लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

unordered_map countt;

bool isPalindromePossible(unordered_map& countt) {
    for (auto key : countt) {
        if (key.second & 1) {
            return false;
        }
        return true;
    }
}

int getMaxPalindrome(string str, unordered_map& 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 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