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 or Next Permutation.

Solution:
1. public class Solution {
2. public List generatePalindromes(String s) {
3. int odd = 0;
4. String mid = "";
5. List res = new ArrayList<>();
6. List list = new ArrayList<>();
7. Map map = new HashMap<>();
8. 9. // step 1. build character count map and count odds
10. for (int i = 0; i < s.length(); i++) {
11. char c = s.charAt(i);
12. map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
13. odd += map.get(c) % 2 != 0 ? 1 : -1;
14. }
15. 16. // cannot form any palindromic string
17. if (odd > 1) return res;
18. 19. // step 2. add half count of each character to list
20. for (Map.Entry entry : map.entrySet()) {
21. char key = entry.getKey();
22. int val = entry.getValue();
23. 24. if (val % 2 != 0) {
25. mid += key;
26. }
27. 28. for (int i = 0; i < val / 2; i++) list.add(key);
29. }
30. 31. // step 3. generate all the permutations O(n!/2)
32. getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
33. 34. return res;
35. }
36. 37. // generate all unique permutation from list
38. void getPerm(List list, String mid, boolean[] used, StringBuilder sb, List res) {
39. if (sb.length() == list.size()) {
40. // form the palindromic string
41. res.add(sb.toString() + mid + sb.reverse().toString());
42. sb.reverse();
43. return;
44. }
45. 46. for (int i = 0; i < list.size(); i++) {
47. // avoid duplication
48. if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) {
49. continue;
50. }
51. 52. if (!used[i]) {
53. used[i] = true;
54. sb.append(list.get(i));
55. 56. getPerm(list, mid, used, sb, res);
57. 58. sb.deleteCharAt(sb.length() - 1);
59. used[i] = false;
60. }
61. }
62. }
63. }