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

For example:

Givens = "aabb", return["abba", "baab"].

Givens = "abc", return[].

tag: DFS

class Solution {

    char single = ' ';
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> hash = new HashMap<>();
        List<String> ans = new ArrayList<>();
        for (char c : s.toCharArray()){
            hash.put(c, hash.getOrDefault(c, 0) + 1);
        }

        if (!valid(hash)) return ans;

        if (single == ' '){
            dfs(s, "", hash, ans);
        }
        else{
            hash.put(single, hash.get(single) - 1);
            dfs(s, single + "", hash, ans);
        }

        return ans;
    }

    private boolean valid(Map<Character, Integer> hash){
        int singleCount = 0;
        for (char c : hash.keySet()){
            if (hash.get(c) % 2 == 1){
                singleCount++;
                single = c;
            }
        }

        return singleCount <= 1;
    }

    private void dfs(String s, String path, Map<Character, Integer> hash, List<String> ans){
        if (path.length() == s.length()){
            ans.add(path);
        }

        for (char c : hash.keySet()){
            if (hash.get(c) > 0){
                hash.put(c, hash.get(c) - 2);
                dfs(s, c + path + c, hash, ans);
                hash.put(c, hash.get(c) + 2);
            }
        }
    }
}

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) return ans;

        Map<Character, Integer> hash = new HashMap<>();
        int total = 0;
        for (char c : s.toCharArray()){
            if (hash.containsKey(c)){
                hash.put(c, hash.get(c) + 1);
            }
            else{
                hash.put(c, 1);
            }
            total++;
        }

        Character oddChar = null;
        for (Character c : hash.keySet()){
            if (hash.get(c) % 2 == 1) {
                if (oddChar != null) return ans;
                oddChar = c;   
            }
        }

        String temp = "";
        if (oddChar != null){
            temp = oddChar + "";
            total -= 1;
        }

        dfs(hash, total, temp, ans);

        return ans;
    }

    private void dfs(Map<Character, Integer> hash, int total, String temp, List<String> ans){
        //System.out.println("temp: " + temp + " total: " + total);

        if (total < 2){
            if (total == 0) ans.add(new String(temp));
            return;
        }



        for (Character c : hash.keySet()){
            if (hash.get(c) < 2) continue;

            hash.put(c, hash.get(c) - 2);
            temp = c + temp + c;
            total -= 2;
            dfs(hash, total, temp, ans);
            hash.put(c, hash.get(c) + 2);
            temp = temp.substring(1, temp.length() - 1);
            total += 2;
        }
    }
}