Palindrome Permutation II

Problem

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Examples

Example 1:

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

Example 2:

Input:
"abc"
Output:
 []

Solution

Method 1 – Backtracking with Frequency Counting

Intuition

A palindrome can be formed from a string if at most one character has an odd count. We can generate half of the palindrome and use backtracking to permute it, then mirror it to form the full palindrome.

Approach

1. Count the frequency of each character in the string.
2. If more than one character has an odd count, return an empty list.
3. Build a half-string using half the count of each character.
4. Use backtracking to generate all unique permutations of the half-string.
5. For each permutation, form the palindrome by mirroring and adding the odd character (if any) in the middle.

Code

C++

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> cnt;
        for (char c : s) cnt[c]++;
        int odd = 0; char mid = 0;
        string half;
        for (auto& [c, v] : cnt) {
            if (v % 2) { odd++; mid = c; }
            half += string(v / 2, c);
        }
        if (odd > 1) return {};
        vector<string> ans;
        sort(half.begin(), half.end());
        do {
            string t = half;
            string rev = t; reverse(rev.begin(), rev.end());
            if (odd) t += mid;
            t += rev;
            ans.push_back(t);
        } while (next_permutation(half.begin(), half.end()));
        return ans;
    }
};

Go

func generatePalindromes(s string) []string {
    cnt := make(map[rune]int)
    for _, c := range s {
        cnt[c]++
    }
    odd := 0
    var mid rune
    half := []rune{}
    for c, v := range cnt {
        if v%2 == 1 {
            odd++
            mid = c
        }
        for i := 0; i < v/2; i++ {
            half = append(half, c)
        }
    }
    if odd > 1 {
        return []string{}
    }
    var ans []string
    var backtrack func([]rune, int)
    used := make([]bool, len(half))
    sort.Slice(half, func(i, j int) bool { return half[i] < half[j] })
    var perm []rune
    backtrack = func(path []rune, depth int) {
        if depth == len(half) {
            t := string(path)
            rev := []rune(t)
            for i, j := 0, len(rev)-1; i < j; i, j = i+1, j-1 {
                rev[i], rev[j] = rev[j], rev[i]
            }
            pal := t
            if odd == 1 {
                pal += string(mid)
            }
            pal += string(rev)
            ans = append(ans, pal)
            return
        }
        for i := 0; i < len(half); i++ {
            if used[i] || (i > 0 && half[i] == half[i-1] && !used[i-1]) {
                continue
            }
            used[i] = true
            backtrack(append(path, half[i]), depth+1)
            used[i] = false
        }
    }
    backtrack([]rune{}, 0)
    return ans
}

Java

class Solution {
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        int odd = 0; char mid = 0;
        StringBuilder half = new StringBuilder();
        for (char c : cnt.keySet()) {
            int v = cnt.get(c);
            if (v % 2 == 1) { odd++; mid = c; }
            for (int i = 0; i < v / 2; i++) half.append(c);
        }
        if (odd > 1) return new ArrayList<>();
        List<String> ans = new ArrayList<>();
        char[] arr = half.toString().toCharArray();
        Arrays.sort(arr);
        boolean[] used = new boolean[arr.length];
        backtrack(ans, new StringBuilder(), arr, used, odd == 1 ? mid : 0);
        return ans;
    }
    private void backtrack(List<String> ans, StringBuilder path, char[] arr, boolean[] used, char mid) {
        if (path.length() == arr.length) {
            String t = path.toString();
            String rev = new StringBuilder(t).reverse().toString();
            String pal = t + (mid != 0 ? mid : "") + rev;
            ans.add(pal);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i] || (i > 0 && arr[i] == arr[i-1] && !used[i-1])) continue;
            used[i] = true;
            path.append(arr[i]);
            backtrack(ans, path, arr, used, mid);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}

Kotlin

class Solution {
    fun generatePalindromes(s: String): List<String> {
        val cnt = mutableMapOf<Char, Int>()
        for (c in s) cnt[c] = cnt.getOrDefault(c, 0) + 1
        var odd = 0; var mid = '\u0000'
        val half = mutableListOf<Char>()
        for ((c, v) in cnt) {
            if (v % 2 == 1) { odd++; mid = c }
            repeat(v / 2) { half.add(c) }
        }
        if (odd > 1) return emptyList()
        val ans = mutableListOf<String>()
        half.sort()
        val used = BooleanArray(half.size)
        fun backtrack(path: MutableList<Char>) {
            if (path.size == half.size) {
                val t = path.joinToString("")
                val rev = t.reversed()
                val pal = t + if (odd == 1) mid else "" + rev
                ans.add(pal)
                return
            }
            for (i in half.indices) {
                if (used[i] || (i > 0 && half[i] == half[i-1] && !used[i-1])) continue
                used[i] = true
                path.add(half[i])
                backtrack(path)
                path.removeAt(path.size - 1)
                used[i] = false
            }
        }
        backtrack(mutableListOf())
        return ans
    }
}

Python

class Solution:
    def generatePalindromes(self, s: str) -> list[str]:
        from collections import Counter
        cnt = Counter(s)
        odd = [c for c in cnt if cnt[c] % 2]
        if len(odd) > 1:
            return []
        mid = odd[0] if odd else ''
        half = []
        for c in cnt:
            half += [c] * (cnt[c] // 2)
        ans = []
        def backtrack(path, used):
            if len(path) == len(half):
                t = ''.join(path)
                pal = t + mid + t[::-1]
                ans.append(pal)
                return
            for i in range(len(half)):
                if used[i] or (i > 0 and half[i] == half[i-1] and not used[i-1]):
                    continue
                used[i] = True
                path.append(half[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
        half.sort()
        backtrack([], [False]*len(half))
        return ans

Rust

impl Solution {
    pub fn generate_palindromes(s: String) -> Vec<String> {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        for c in s.chars() {
            *cnt.entry(c).or_insert(0) += 1;
        }
        let mut odd = 0;
        let mut mid = None;
        let mut half = Vec::new();
        for (&c, &v) in &cnt {
            if v % 2 == 1 {
                odd += 1;
                mid = Some(c);
            }
            for _ in 0..v/2 {
                half.push(c);
            }
        }
        if odd > 1 {
            return vec![];
        }
        half.sort();
        let mut ans = Vec::new();
        let mut used = vec![false; half.len()];
        fn backtrack(half: &Vec<char>, used: &mut Vec<bool>, path: &mut Vec<char>, ans: &mut Vec<String>, mid: Option<char>) {
            if path.len() == half.len() {
                let t: String = path.iter().collect();
                let mut pal = t.clone();
                if let Some(m) = mid {
                    pal.push(m);
                }
                pal.extend(t.chars().rev());
                ans.push(pal);
                return;
            }
            for i in 0..half.len() {
                if used[i] || (i > 0 && half[i] == half[i-1] && !used[i-1]) {
                    continue;
                }
                used[i] = true;
                path.push(half[i]);
                backtrack(half, used, path, ans, mid);
                path.pop();
                used[i] = false;
            }
        }
        backtrack(&half, &mut used, &mut Vec::new(), &mut ans, mid);
        ans
    }
}

TypeScript

class Solution {
    generatePalindromes(s: string): string[] {
        const cnt: Record<string, number> = {};
        for (const c of s) cnt[c] = (cnt[c] || 0) + 1;
        const odd = Object.keys(cnt).filter(c => cnt[c] % 2);
        if (odd.length > 1) return [];
        const mid = odd[0] || '';
        let half: string[] = [];
        for (const c in cnt) {
            half = half.concat(Array(cnt[c] >> 1).fill(c));
        }
        half.sort();
        const ans: string[] = [];
        const used: boolean[] = Array(half.length).fill(false);
        function backtrack(path: string[]) {
            if (path.length === half.length) {
                const t = path.join('');
                ans.push(t + mid + t.split('').reverse().join(''));
                return;
            }
            for (let i = 0; i < half.length; i++) {
                if (used[i] || (i > 0 && half[i] === half[i-1] && !used[i-1])) continue;
                used[i] = true;
                path.push(half[i]);
                backtrack(path);
                path.pop();
                used[i] = false;
            }
        }
        backtrack([]);
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * n!) — Generating all unique permutations of half the string (with deduplication).
• 🧺 Space complexity: O(n * n!) — For storing all palindromic permutations.