প্যালিনড্রোম পারমুটেশন করার ন্যূনতম ক্যারেক্টার রিমুভাল C++-তে

সমস্যা বিবরণ

একটি স্ট্রিং S দেওয়া আছে, আমাদের ন্যূনতম কত ক্যারেক্টার সরাতে হবে যাতে স্ট্রিং S-এর যেকোনো পারমুটেশন প্যালিনড্রোম হয়।

উদাহরণ

str = "abcdba" হলে ১ ক্যারেক্টার সরাতে হবে (c বা d)।

অ্যালগরিদম

1. প্যালিনড্রোম দুই ধরণের হয়: জোড় দৈর্ঘ্য এবং বিজোড় দৈর্ঘ্য।
2. জোড় দৈর্ঘ্যের প্যালিনড্রোমে প্রতিটি ক্যারেক্টার জোড় বার থাকতে হয়।
3. বিজোড় দৈর্ঘ্যের প্যালিনড্রোমে একটি ক্যারেক্টার বিজোড় বার থাকতে পারে, বাকিগুলো জোড় বার।
4. প্রতিটি ক্যারেক্টার এর ফ্রিকোয়েন্সি চেক করুন এবং বিজোড় ফ্রিকোয়েন্সি বালা ক্যারেক্টারগুলো গণনা করুন। ফলাফল = বিজোড় ফ্রিকোয়েন্সি বালা ক্যারেক্টার সংখ্যা - ১।

উদাহরণ

#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