267. Palindrome Permutation II - Leetcode Solution

Problem Description

Given a string s, return all the palindromic permutations (without duplicates) of s. You may return the answer in any order. If no palindromic permutation is possible, return an empty list.

A palindrome is a string that reads the same backward as forward.
Each character in s must be used exactly as many times as it appears in the input.
You must not reuse characters beyond their count and should not return duplicate permutations.

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

Thought Process

The first idea that may come to mind is to generate all possible permutations of the string and check which ones are palindromes. However, this brute-force approach is not efficient, especially for longer strings.

To optimize, notice that a palindrome is symmetric: the left half is the reverse of the right half. This means that for a string to have a palindromic permutation:

If the length is even, every character must appear an even number of times.
If the length is odd, only one character can appear an odd number of times (and it will be in the center).

With this insight, we only need to generate half of the palindrome (the left half), and then mirror it to get the full palindrome. This approach avoids unnecessary work and duplicate results.

Solution Approach

Here is a step-by-step breakdown of the optimized algorithm:

Count character frequencies:
- Use a hash map (dictionary) to count how many times each character appears in s.
Check palindrome possibility:
- Count how many characters have odd frequencies.
- If more than one character has an odd count, return an empty list (no palindromic permutation is possible).
Prepare for permutation:
- For each character, take half its count (since the other half will be mirrored).
- Collect these half-characters into a list to be permuted.
- If there is a character with an odd count, remember it to be placed in the middle of the palindrome.
Generate unique half-permutations:
- Use backtracking to generate all unique permutations of the half-list. Use a boolean array or a set to avoid duplicates.
Build full palindromes:
- For each unique half-permutation, form the palindrome by concatenating the half, the middle character (if any), and the reverse of the half.
Return the list of palindromic permutations.

We use a hash map for O(1) character lookups and backtracking to generate unique permutations efficiently.

Example Walkthrough

Let's walk through the input "aabb":

Count frequencies: {'a': 2, 'b': 2}
Check odd counts: Both have even counts, so a palindrome is possible.
Prepare half: Take one 'a' and one 'b' (half of each character): ['a', 'b']
Permute half:
- Unique permutations: ["ab", "ba"]
Build palindromes:
- "ab" + "" + "ba" = "abba"
- "ba" + "" + "ab" = "baab"
Return: ["abba", "baab"]

If given "abc", since all three characters have odd counts, no palindromic permutation is possible, so we return [].

Code Implementation

from collections import Counter

class Solution:
    def generatePalindromes(self, s: str):
        count = Counter(s)
        mid = ''
        halves = []
        for char, freq in count.items():
            if freq % 2:
                if mid:
                    return []
                mid = char
            halves += [char] * (freq // 2)
        res = []
        used = [False] * len(halves)
        halves.sort()
        def backtrack(path):
            if len(path) == len(halves):
                half = ''.join(path)
                res.append(half + mid + half[::-1])
                return
            for i in range(len(halves)):
                if used[i]:
                    continue
                if i > 0 and halves[i] == halves[i-1] and not used[i-1]:
                    continue
                used[i] = True
                path.append(halves[i])
                backtrack(path)
                path.pop()
                used[i] = False
        backtrack([])
        return res

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        string mid = "";
        vector<char> halves;
        for (auto &p : count) {
            if (p.second % 2) {
                if (!mid.empty()) return {};
                mid = p.first;
            }
            for (int i = 0; i < p.second / 2; ++i)
                halves.push_back(p.first);
        }
        sort(halves.begin(), halves.end());
        vector<string> res;
        vector<bool> used(halves.size(), false);
        function<void(string&)> backtrack = [&](string &path) {
            if (path.size() == halves.size()) {
                string rev = path;
                reverse(rev.begin(), rev.end());
                res.push_back(path + mid + rev);
                return;
            }
            for (int i = 0; i < halves.size(); ++i) {
                if (used[i]) continue;
                if (i > 0 && halves[i] == halves[i-1] && !used[i-1]) continue;
                used[i] = true;
                path.push_back(halves[i]);
                backtrack(path);
                path.pop_back();
                used[i] = false;
            }
        };
        string path;
        backtrack(path);
        return res;
    }
};

import java.util.*;

public class Solution {
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray())
            count.put(c, count.getOrDefault(c, 0) + 1);
        String mid = "";
        List<Character> halves = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : count.entrySet()) {
            if (entry.getValue() % 2 == 1) {
                if (!mid.isEmpty()) return new ArrayList<>();
                mid = entry.getKey().toString();
            }
            for (int i = 0; i < entry.getValue() / 2; ++i)
                halves.add(entry.getKey());
        }
        Collections.sort(halves);
        List<String> res = new ArrayList<>();
        boolean[] used = new boolean[halves.size()];
        backtrack(res, new StringBuilder(), halves, used, mid);
        return res;
    }
    private void backtrack(List<String> res, StringBuilder path, List<Character> halves, boolean[] used, String mid) {
        if (path.length() == halves.size()) {
            String half = path.toString();
            res.add(half + mid + new StringBuilder(half).reverse().toString());
            return;
        }
        for (int i = 0; i < halves.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && halves.get(i) == halves.get(i-1) && !used[i-1]) continue;
            used[i] = true;
            path.append(halves.get(i));
            backtrack(res, path, halves, used, mid);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}

var generatePalindromes = function(s) {
    const count = {};
    for (let c of s) count[c] = (count[c] || 0) + 1;
    let mid = '';
    let halves = [];
    for (let c in count) {
        if (count[c] % 2) {
            if (mid) return [];
            mid = c;
        }
        for (let i = 0; i < Math.floor(count[c]/2); ++i)
            halves.push(c);
    }
    halves.sort();
    const res = [];
    const used = new Array(halves.length).fill(false);
    function backtrack(path) {
        if (path.length === halves.length) {
            const half = path.join('');
            res.push(half + mid + half.split('').reverse().join(''));
            return;
        }
        for (let i = 0; i < halves.length; ++i) {
            if (used[i]) continue;
            if (i > 0 && halves[i] === halves[i-1] && !used[i-1]) continue;
            used[i] = true;
            path.push(halves[i]);
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    }
    backtrack([]);
    return res;
};

Time and Space Complexity

Brute-force Approach:
- Time: O(n!) for generating all permutations, where n is the length of s.
- Space: O(n!) for storing all possible permutations.
Optimized Approach:
- Time: O((n/2)!) where n is the length of s, since we only permute half the characters (with deduplication).
- Space: O((n/2)!) for storing unique palindromic permutations, plus O(n) for auxiliary data structures.
The reduction in problem size (by permuting only half) and deduplication via sorting and used-tracking makes the solution efficient for moderate input sizes.

Summary

The key insight for generating palindromic permutations is to leverage the symmetric property of palindromes. By checking character frequencies, we can quickly determine if a palindrome is possible. Then, by generating unique permutations of half the string and mirroring them, we efficiently construct all valid palindromic permutations without duplicates. This approach is much more elegant and scalable than brute-force permutation.

AlgoMap.io

Want Help Cracking FAANG?