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.

Example 1:

1
2
3
4


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

Example 2:

1
2
3
4


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


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;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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.

Problem#

Solution#

Method 1 – Backtracking with Frequency Counting#

Intuition#

Approach#

Code#

Complexity#