public class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new ArrayList<String>();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int odd = 0;
// The firstHalf's length is s.length() / 2
char[] array = new char[s.length() / 2];
int cur = 0;
String mid = "";
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
char key = entry.getKey();
int freq = entry.getValue();
if (freq % 2 == 1) {
odd++;
mid = mid + key;
}
for (int i = 0; i < freq / 2; i++) {
array[cur++] = key;
}
}
if (odd > 1) {
return result;
}
getPerm(result, array, mid, 0);
return result;
}
private void getPerm(List<String> result, char[] array, String mid, int index) {
if (index == array.length) {
// String class doesn't have reverse method, so change it to StringBuffer, use reverse() and toString()
String firstHalf = new String(array, 0, array.length);
String secondHalf = new StringBuffer(firstHalf).reverse().toString();
result.add(firstHalf + mid + secondHalf);
return;
}
Set<Character> set = new HashSet<Character>();
for (int i = index; i < array.length; i++) {
if (set.add(array[i])) {
swap(array, index, i);
getPerm(result, array, mid, index + 1);
swap(array, index, i);
}
}
}
private void swap (char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}