Kটি প্যালিনড্রোম স্ট্রিং তৈরি করা C++-এ

সমস্যা বিবরণ

একটি স্ট্রিং s এবং সংখ্যা k দেওয়া আছে। s-এর সকল অক্ষর ব্যবহার করে কি kটি নন-এম্পটি প্যালিনড্রোম স্ট্রিং তৈরি করা সম্ভব? প্রতিটি অক্ষর ঠিক একবার ব্যবহার করতে হবে।

মূল পর্যবেক্ষণ

• একটি প্যালিনড্রোমে সর্বোচ্চ একটি অক্ষর বিজোড়বার আসতে পারে (মধ্যে)।
• অতএব, s-এ বিজোড় ফ্রিকোয়েন্সি वालা অক্ষরের সংখ্যা যদি k-এর চেয়ে বেশি হয়, তবে অসম্ভব।
• যদি s.length() < k হয়, তবে অসম্ভব (প্রতিটি প্যালিনড্রোমে কমপক্ষে এক অক্ষর লাগবে)।
• যদি s.length() == k হয়, তবে সবসময় সম্ভব (প্রতিটি অক্ষর আলাদা প্যালিনড্রোম)।

অ্যালগরিদম

1. n = s.length()। যদি n < k হয় → false।
2. যদি n == k হয় → true।
3. প্রতিটি অক্ষরের ফ্রিকোয়েন্সি গণনা করুন (แมপ ব্যবহার করে)।
4. বিজোড় ফ্রিকোয়েন্সি वाले অক্ষরের সংখ্যা odd হিসাব করুন।
5. যদি odd <= k হয় → true, অন্যথায় false।

C++ বাস্তবায়ন

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

class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size();
        if (n < k) return false;
        if (n == k) return true;

        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int odd = 0;
        for (auto& p : freq)
            if (p.second & 1) odd++;

        return odd <= k;
    }
};

int main() {
    Solution ob;
    cout << ob.canConstruct("true", 4); // আউটপুট: 1 (true)
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n) — স্ট্রিং একবার ট্রাভার্সাল।
• স্থান জটিলতা: O(1) — সর্বোচ্চ ২৬টি অক্ষরের জন্য ম্যাপ (কনস্ট্যান্ট)।