Palindrome Permutation II

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

For example:

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

Given s = "abc", return [].

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II orNext Permutation.

Count the occurrence of the string, if there are more than one odd number of occurrences in the string, return empty result. Otherwise start from middle and add chars to two sides until we reach the length.

public List<string> generatePalindromes(String s) {
        List<string> rst = new ArrayList<>();
        if (s.length() == 0) {
            return rst;
        }

        Map<character, integer> countChars = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (!countChars.containsKey(c)) {
                countChars.put(c, 1);
            } else {
                countChars.put(c, countChars.get(c) + 1);
            }
        }
        char[] chars = new char[countChars.size()];
        char single = '$';
        int index = 0;
        boolean containsSingle = false;
        for (char c : countChars.keySet()) {
            if (countChars.get(c) % 2 != 0) {
                if (containsSingle) {
                    return rst;
                } else {
                    single = c;
                    containsSingle = true;
                }
            } else {
                chars[index++] = c;
            }
        }
        if (containsSingle) {
            getList(chars,  "" + single, rst, s.length(), chars.length - 1);
        } else {
            getList(chars, "", rst, s.length(), chars.length);
        }
        return rst;
    }

    private void getList(char[] chars,  String curr, List<string> rst, int length, int size) {
        if (curr.length() == length){
            rst.add(curr);
            return;
        }
        for (int i = 0; i < size; i++) {
            char c = chars[i];
            if (curr.indexOf(c) >= 0) {
                continue;
            }
            getList(chars, c + curr + c, rst, length, size);
        }
    }