Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
Example 1:
Input: "aabb"
Output: ["abba", "baab"]
Example 2:
Input: "abc"
Output: []
// Backtracking
void backtracking(const string& halves, const string& mid, vector<bool>& used, string& first_half, vector<string>& res) {
if (first_half.length() == halves.length()) {
res.push_back(first_half + mid + string(first_half.rbegin(), first_half.rend()));
return;
}
for (int i = 0; i < halves.length(); ++i) {
if (i > 0 && halves[i] == halves[i - 1] && !used[i - 1]) continue;
if (!used[i]) {
used[i] = true;
first_half.push_back((char)halves[i]);
// Recursion
backtracking(halves, mid, used, first_half, res);
// Backtrack
first_half.pop_back();
used[i] = false;
}
}
}
vector<string> generatePalindromes(string s) {
int odd = 0;
vector<string> res;
string halves, mid, first_half;
vector<int> record(128, 0);
// Build record and count odd
for (char ch : s) {
if (++record[ch] & 1) odd += 1;
else odd -= 1;
}
// Cannot generate any palindromic string
if (odd > 1) return res;
// Add half palindrome to halves
for (int ch = 0; ch < 128; ++ch) {
if (record[ch] & 1) mid += (char)ch;
for (int i = 0; i < record[ch] / 2; ++i) halves.push_back((char)ch);
}
// Generate all permutations
vector<bool> used(halves.size(), false);
backtracking(halves, mid, used, first_half, res);
return res;
}