267

267. Palindrome Permutation II (Medium)

Given a string s, return all the palindromic permutations (without duplicates) of it.

You may return the answer in any order. If s has no palindromic permutation, return an empty list.

 

Example 1:

Input: s = "aabb"
Output: ["abba","baab"]

Example 2:

Input: s = "abc"
Output: []

 

Constraints:

• 1 <= s.length <= 16
• s consists of only lowercase English letters.

Companies: Cruise Automation, Amazon, Google

Related Topics:
Hash Table, String, Backtracking

Similar Questions:

• Next Permutation (Medium)
• Permutations II (Medium)
• Palindrome Permutation (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/palindrome-permutation-ii
// Author: github.com/lzl124631x
// Time: O(8! * 26)
// Space: O(16)
class Solution {
public:
    vector<string> generatePalindromes(string s) {
        int cnt[26] = {}, odd = -1, len = 0;
        for (char c : s) cnt[c - 'a']++;
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] % 2) {
                if (odd != -1) return {};
                odd = i;
            }
            len += cnt[i] / 2;
        }
        vector<string> ans;
        string tmp;
        function<void()> dfs = [&]() {
            if (tmp.size() == len) {
                string r(rbegin(tmp), rend(tmp));
                ans.push_back(tmp + (odd != -1 ? string(1, 'a' + odd) : "") + r);
                return;
            }
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] == 0 || cnt[i] == 1) continue;
                cnt[i] -= 2;
                tmp.push_back('a' + i);
                dfs();
                tmp.pop_back();
                cnt[i] += 2;
            }
        };
        dfs();
        return ans;
    }
};