समस्या कथन
एक स्ट्रिंग S को देखते हुए, हमें न्यूनतम वर्ण खोजने होंगे जिन्हें हम स्ट्रिंग S के किसी भी क्रमपरिवर्तन को एक पैलिंड्रोम बनाने के लिए हटा सकते हैं
उदाहरण
यदि str ="abcdba" है तो हम 1 वर्ण यानी 'c' या 'd' को हटा देते हैं।
एल्गोरिदम
1. There can be two types of a palindrome, even length, and odd length palindromes 2. We can deduce the fact that an even length palindrome must have every character occurring even number of times 3.An odd palindrome must have every character occurring even number of times except one character occurring odd number of time 4. Check the frequency of every character and those characters occurring odd number of times are then counted. Then the result is total count of odd frequency characters’ minus 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 << "Minimum characters to be removed = " <<
minCharactersRemoved(str) << endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है
आउटपुट
Minimum characters to be removed = 1