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

Analysis:

Should ask if the chars contains only letters, lowercase letters or any char.

Solution:

 1 import java.util.Map.Entry;
 2 
 3 public class Solution {
 4     public List<String> generatePalindromes(String s) {
 5         List<String> resList = new ArrayList<String>();
 6         if (s.isEmpty())
 7             return resList;
 8 
 9         HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
10         for (int i = 0; i < s.length(); i++) {
11             char curChar = s.charAt(i);
12             int count = charMap.getOrDefault(curChar, 0);
13             charMap.put(curChar, count + 1);
14         }
15         int[] counts = new int[charMap.size()];
16         char[] chars = new char[charMap.size()];
17         int ind = 0;
18         for (Entry entry : charMap.entrySet()) {
19             chars[ind] = (char) entry.getKey();
20             counts[ind++] = (int) entry.getValue();
21         }
22 
23         // If there is more than one odd count, fail.
24         boolean hasOdd = false;
25         int oddIndex = -1;
26         for (int i = 0; i < counts.length; i++)
27             if (counts[i] % 2 == 1) {
28                 if (hasOdd)
29                     return resList;
30                 hasOdd = true;
31                 oddIndex = i;
32             }
33 
34         StringBuilder builder = new StringBuilder();
35 
36         int leftLen = s.length();
37         if (hasOdd) {
38             char c = chars[oddIndex];
39             counts[oddIndex]--;
40             builder.append(c);
41             leftLen--;
42         }
43 
44         getPalindromes(chars, counts, leftLen, builder, resList);
45         return resList;
46     }
47 
48     public void getPalindromes(char[] chars, int[] counts, int leftLen, StringBuilder builder,
49             List<String> resList) {
50         if (leftLen == 0) {
51             resList.add(builder.toString());
52             return;
53         }
54 
55         for (int i = 0; i < counts.length; i++)
56             if (counts[i] > 0) {
57                 char curChar = chars[i];
58                 counts[i] -= 2;
59                 builder.insert(0, curChar);
60                 builder.append(curChar);
61                 getPalindromes(chars, counts, leftLen - 2, builder, resList);
62                 builder.deleteCharAt(builder.length() - 1);
63                 builder.deleteCharAt(0);
64                 counts[i] += 2;
65             }
66     }
67 }