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 [].

Solution

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

        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.merge(c, 1, (a, b) -> a + b);
        }

        int oddCount = 0;
        for (Character key : map.keySet()) {
            if (map.get(key) % 2 == 1) {
                oddCount += 1;
            }
        }

        if (oddCount > 1) {
            return result;
        }

        List<Character> characters = new ArrayList<>();
        Character oddChar = null;
        for (Character key : map.keySet()) {
            for (int x = 0; x < map.get(key) / 2; x++) {
                characters.add(key);
            }

            if (map.get(key) % 2 == 1) {
                oddChar = key;
            }
        }

        List<String> left = generatePermutations(characters);
        List<String> finalResult = new ArrayList<>();
        for (int i = 0; i < left.size(); i++) {
            StringBuffer sb = new StringBuffer();
            String current = left.get(i);
            sb.append(current);
            if (oddChar != null) {
                sb.append(String.valueOf(oddChar));
            }
            sb.append(new StringBuffer(current).reverse());
            finalResult.add(sb.toString());
        }

        return finalResult;
    }

    private List<String> generatePermutations(List<Character> characters) {
        Collections.sort(characters);
        Set<String> result = new HashSet<>();
        helper(characters, 0, new StringBuffer(), result);
        return result.stream().collect(Collectors.toList());
    }

    private void helper(List<Character> characters, int current, StringBuffer stringBuffer, Set<String> result) {
        if (current == characters.size()) {
            result.add(stringBuffer.toString());
            return;
        }

        Character ch = characters.get(current);
        for (int j = 0; j <= stringBuffer.length(); j++) {
            stringBuffer.insert(j, ch);
            helper(characters, current + 1, stringBuffer, result);
            stringBuffer.deleteCharAt(j);
        }
    }
}