C++-এ Palindrome Permutation II: স্ট্রিংর সব প্যালিনড্রোমিক পারমুটেশন জেনারেট করা

একটি স্ট্রিং s দেওয়া আছে। এর সব প্যালিনড্রোমিক পারমুটেশন (Palindromic Permutations) জেনারেট করতে হবে, ডুপ্লিকেট ছাড়া। যদি কোনো প্যালিনড্রোমিক পারমুটেশন সম্ভব না হয়, তবে খালি লিস্ট রিটার্ন করুন।

উদাহরণ

ইনপুট: "aabb"

আউটপুট: ["abba", "baab"]

সমাধানের পদ্ধতি (Backtracking + Character Count)

1. ক্যারেক্টার ফ্রিকোয়েন্সি ম্যাপ cnt বানান।
2. অড ফ্রিকোয়েন্সি वाले ক্যারেক্টারগুলো গুনুন। যদি > ১ হয়, তবে প্যালিনড্রোম সম্ভব নয় → খালি রিটার্ন।
3. একটি টেমপ্লেট স্ট্রিং temp (সাইজ n, '*' দিয়ে ফিলড) তৈরি করুন।
4. রিকারসিভ ব্যাকট্র্যাকিং solve(s, sz, m, idx):
   • sz = বাকি পূরণের সাইজ, idx = বাম পাশের ইনডেক্স।
   • যদি sz == 0, তবে প্যালিনড্রোম কমপ্লিট → ret-এ পুশ করুন।
   • ফ্রিকোয়েন্সি ম্যাপ থেকে:
     • ফ্রিক ০ হলে স্কিপ।
     • ফ্রিক ১ হলে (অড ক্যারেক্টার) -> মাঝপথে রাখার জন্য সেভ করুন।
     • ফ্রিক >= ২ হলে (ইভেন পেয়ার) -> s[idx] এবং s[n-1-idx] এ রাখুন, ফ্রিক ২ কমিয়ে রিকারসিভ কল, ব্যাকট্র্যাক।
   • যদি কোনো ইভেন পেয়ার ব্যবহার না হয় (অড লেন্থের মাঝপথ), তবে সেভ করা অড ক্যারেক্টার s[idx]-এ রাখুন এবং রিকারসিভ কল।
5. ret রিটার্ন করুন।

C++ কোড উদাহরণ

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

void print_vector(vector<string> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++)
        cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> ret;
    
    void solve(string s, int sz, unordered_map<char,int>& m, int idx = 0) {
        if (sz == 0) {
            ret.push_back(s);
            return;
        }
        bool evenFound = false;
        char oddChar;
        unordered_map<char, int>::iterator it = m.begin();
        set<char> visited;
        
        while (it != m.end()) {
            if (!it->second) { it++; continue; }
            else if (it->second == 1) {
                oddChar = it->first;
            } else {
                if (visited.count(it->first)) continue;
                s[idx] = it->first;
                s[s.size() - 1 - idx] = it->first;
                evenFound = true;
                m[it->first] -= 2;
                solve(s, sz - 2, m, idx + 1);
                m[it->first] += 2;
                visited.insert(it->first);
            }
            it++;
        }
        if (!evenFound) {
            s[idx] = oddChar;
            solve(s, sz - 1, m, idx + 1);
        }
    }
    
    vector<string> generatePalindromes(string s) {
        unordered_map<char,int> cnt;
        int n = s.size();
        string temp = "";
        for (int i = 0; i < n; i++) {
            cnt[s[i]]++;
            temp += "*";
        }
        int oddCnt = 0;
        for (auto it = cnt.begin(); it != cnt.end(); it++)
            oddCnt += (it->second & 1);
        if (oddCnt > 1) return ret;
        solve(temp, n, cnt);
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.generatePalindromes("aabb"));
    return 0;
}

ইনপুট

"aabb"

আউটপুট

[baab, abba, ]