समस्या कथन
एक स्ट्रिंग S दी गई है, हमें न्यूनतम वर्ण खोजने हैं जिन्हें हम हटा सकते हैं ताकि स्ट्रिंग S का कोई भी परम्यूटेशन पेलिंड्रोम बन जाए
उदाहरण
यदि str = "abcdba" तो हम 1 वर्ण हटाते हैं यानी या तो 'c' या 'd'।
एल्गोरिदम
1. पेलिंड्रोम दो प्रकार के हो सकते हैं, सम लंबाई, और विषम लंबाई पेलिंड्रोम 2. हम इस तथ्य को निकाल सकते हैं कि एक सम लंबाई पेलिंड्रोम में प्रत्येक वर्ण सम संख्या में बार आना चाहिए 3. एक विषम पेलिंड्रोम में प्रत्येक वर्ण सम संख्या में बार आना चाहिए सिवाय एक वर्ण के जो विषम संख्या में बार आता है 4. प्रत्येक वर्ण की आवृत्ति जांचें और विषम संख्या में आने वाले वर्णों को गिनें। फिर परिणाम विषम आवृत्ति वाले वर्णों की कुल संख्या घटा 1 है
उदाहरण
#include <bits/stdc++.h> #define MAX 26 using namespace std; int minCharactersRemoved(string str) { int hash[MAX] = {0}; for (int i = 0; str[i]; ++i) { hash[str[i] - 'a']++; } int cnt = 0; for (int i = 0; i < MAX; ++i) { if (hash[i] & 1) { ++cnt; } } return (cnt == 0) ? 0 : (cnt - 1); } int main(){ string str = "abcdba"; cout << "हटाए जाने वाले न्यूनतम वर्ण = " << minCharactersRemoved(str) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
हटाए जाने वाले न्यूनतम वर्ण = 1
