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

Given s = "aabb", return ["abba","baab"].

Solution

class Solution {    public List
    
      generatePalindromes(String s) {        List
     
       res = new ArrayList<>();        if (s == null || s.length() == 0) return res;                //create a map to record counts of chars: int[256]        //count the chars that have odd number of count: <= 1 means valid palindrome        int[] map = new int[256];        int odd = 0;        for (char ch: s.toCharArray()) {            map[ch]++;            if ((map[ch]&1) == 1) odd++;            else odd--;        }        if (odd > 1) return res;                //get mid string: should have length of 1 or 0        String mid = "";        int halfLen = 0;        for (int i = 0; i < 256; i++) {            if (map[i] > 0) {                //find the odd counted char, add to mid                if ((map[i]&1) == 1) {                    mid += (char)i;                    map[i]--;                }                //reduce count to half for each char                map[i] /= 2;                //update half palindrome length                halfLen += map[i];            }        }                dfs(map, "", mid, halfLen, res);        return res;    }        private void dfs(int[] map, String temp, String mid, int len, List
      
        res) {        if (temp.length() == len) {            StringBuilder sb = new StringBuilder(temp).reverse();            res.add(temp+mid+sb.toString());            return;        }        for (int i = 0; i < 256; i++) {            if (map[i] > 0) {                map[i]--;                dfs(map, temp+(char)i, mid, len, res);                map[i]++;            }        }    }}