# Leetcode 267 Solution

https://leetcode.com/problems/palindrome-permutation-ii

## Solution

``````class Solution {
public:
void generatePalindromes(string& curr, int from, vector<string>& res, char middle_ch)
{
if (from == curr.size())
{
string right = curr;
reverse(right.begin(), right.end());

string s = middle_ch == 0 ? curr + right : curr + string(1, middle_ch) + right;
res.push_back(s);
return;
}

unordered_set<char> visited;
for (int i = from; i < curr.size(); i++)
{
if (visited.find(curr[i]) != visited.end())
continue;

visited.insert(curr[i]);
swap(curr[i], curr[from]);
generatePalindromes(curr, from + 1, res, middle_ch);
swap(curr[i], curr[from]);
}
}

vector<string> generatePalindromes(string s) {
unordered_map<char, int> m;

for (auto ch : s)
m[ch]++;

int evenCnt = 0;
for (auto pair : m)
evenCnt += pair.second % 2;

vector<string> res;
if (s.size() % 2 == 0 && evenCnt > 0 || s.size() % 2 == 1 && evenCnt > 1)
return res;

string curr;
char middle_ch = 0;
for (auto pair : m)
{
if (pair.second / 2)
curr += string(pair.second / 2, pair.first);

if (pair.second % 2 == 1)
middle_ch = pair.first;
}

sort(curr.begin(), curr.end());

generatePalindromes(curr, 0, res, middle_ch);

return res;
}
};
``````