# Accepted java solution.

• public class Solution {
public List<String> generatePalindromes(String s) {

if (s == null || s.length() == 0)
return new ArrayList<String>();

// Odd string length would mean one character that stays in center for all palindromes.
boolean odd = s.length() % 2 == 1;

// Count each character, how many times it occurs in string.
HashMap<Character, Integer> chars = new HashMap<Character, Integer>();
int size = 0;
for (char ch : s.toCharArray()) {

Integer count = chars.get(ch);
if (count == null) {
chars.put (ch, 1);
} else {
int val = count.intValue();
chars.put (ch, ++val);
}
}

// create new character array with unique characters for left half of palindrome to generate all permutations. A unique character appears once if it appears 2 times in the original string. A unique character may appear more than once if the count of that character is more than 2. If a unique character has odd count like 1 or 3 then it will appear in center and if odd count is > 1 then that character is additionally added correspondingly to the new character array. Also center occurance is remembered in the variable oddOne.

for (int i : chars.values()) {
if (i % 2 == 1) {
size+= i/2;
if (odd)
odd = false;
else // More than one character has odd count or string is even length and so no palindrome possible
return new ArrayList<String>();
} else {
size += i / 2;
}
}
char[] newArray = new char[size];
int index = 0;
char oddOne = 0;
for (Map.Entry<Character,Integer> m : chars.entrySet()) {
Integer val = m.getValue();
Character c = m.getKey();
if (val.intValue() %2 == 1) {
oddOne = c;
for (int k = 0; k < val.intValue()/2; k++) {
newArray[index++] = c;
}
} else {
for (int k = 0; k < val.intValue()/2; k++) {
newArray[index++] = c;
}
}
}
return generatePermutations(newArray, 0, oddOne);
}

List<String> generatePermutations (char[] array, int i, char oddOne) {

// > is needed in case array length is 0 which is the case when there is only one character in string.
if (i >= (array.length - 1) ){
StringBuffer str = new StringBuffer();
for (int j = 0 ; j < array.length; j++) {
str.append(array[j]);
}

// center of palindrome when original string length is odd
if (oddOne != 0) {
str.append(oddOne);
}
// generate the rest of the palindrome by taking left side and reversing it and adding to the array.
for (int j = array.length - 1; j >= 0; j--) {
str.append(array[j]);
}
ArrayList<String> list =  new ArrayList<String>();
return list;
} else {
ArrayList<String> list = new ArrayList<String>();
for (int j = i; j < array.length; j++) {
// don't regenerate permutations swapping with same character in a different position to avoid duplicates.
if (array[j] == array[i] && i != j)
continue;
swap (i, j, array);
list.addAll (generatePermutations(array, i+1, oddOne));
swap (i, j, array);
}
return list;
}

}
void swap (int i, int j, char[] array) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.