[LintCode] Problem 917 - 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.

Example

No.1

Input: s = “aabb”

Output: [“abba”,”baab”]

No.2

Input: “abc”

Output: []

Code

public List<String> generatePalindromes(String s) {
    List<String> result = new ArrayList<>();
    Map<Character, Integer> map = new HashMap<>();
    int count = 0;
    String odd = "";
    List<Character> half = new ArrayList<>();

    for (Character ch : s.toCharArray())
        map.put(ch, map.getOrDefault(ch, 0) + 1);

    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
        Character key = entry.getKey();
        Integer value = entry.getValue();
        
        if (value % 2 != 0) {
            count++;

            if (count > 1)
                return result;

            odd = String.valueOf(key);
        }
        
        for (int i = 0; i < value / 2; i++)
            half.add(key);
    }

    permutation(result, half, odd, new StringBuilder(), new boolean[half.size()]);

    return result;
}

private void permutation(List<String> result, List<Character> half, String odd, StringBuilder sb, boolean[] visit) {
    if (sb.length() == half.size()) {
        result.add(sb.toString() + odd + sb.reverse().toString());
        sb.reverse();
        return;
    }

    for (int i = 0; i < half.size(); i++) {
        if (i > 0 && half.get(i) == half.get(i - 1) && !visit[i - 1])
            continue;
            
        if (!visit[i]) {
            visit[i] = true;
            sb.append(half.get(i));
            permutation(result, half, odd, sb, visit);
            sb.deleteCharAt(sb.length() - 1);
            visit[i] = false;
        }
    }
}