
First we need to make sure if "s" is a valid input for generating palindromes. countPalindrome() will return a StringBuilder containing half of letters in "s" if "s" is valid and s.length is an even number; or return s.length  1 letters if s.length is an odd number; If "s" is not a valid input, a null will be returned;
At the same time "charCenter " will be set to the center letter if a valid input string's length is odd, or '0' if it is not valid;
eg. s = "aabbcc" return "abc" charCenter = '0', s = "123123d" return "123" charCenter = 'd'
s = "abcv" return null; 
After getting those half valid letters and a charCenter, we can use backtrack method to generate all permutations of those letters, and get the answer by adding their reversed strings to their tails;
public class Solution {
static int Len;
static char charCenter;
static final int R = 128;//128 is enought for this problem
public static List<String> generatePalindromes(String s) {
List<String> list = new ArrayList<>();
if(s == null  s.length() == 0)
return list;
StringBuilder sb1 = countPalindrome(s);//get those half valid letters or null if s is not valid input
if(sb1 == null)
return list;
s = sb1.toString();//replace the string with what we got.
char[] charArr = s.toCharArray();
Len = charArr.length;
boolean[] visited = new boolean[Len];//used to mark what letters are visited
Arrays.sort(charArr);
StringBuilder sb2 = new StringBuilder();
backtrack(charArr,list,visited,sb2);
return list;
}
public static StringBuilder countPalindrome(String s)
{
int[] count = new int[R];
char[] charArr = s.toCharArray();
StringBuilder sb = new StringBuilder();
Arrays.sort(charArr);//sort it for the convenience of latter use, does not really matter
int single = 0;
for(int i = 0 ; i < charArr.length; i++)
{
int index = charArr[i];
count[index] += 1;//use the letter's ASCII as index of count
single++;
if(count[index] == 2)
{
count[index] = 0;
single = 2;//single minus 2 not 1, because you counted every letter you are dealing with
sb.append(charArr[i]);//append the letter in sb when we got two of them
}
}
if(single > 1) return null;//there should be only 0 or 1 center for a valid string
else if(single == 1)//find the center if there is one.
{
for(int i = 0; i < R; i++)
{
if(count[i] == 1)
{
charCenter = (char)(i);
}
}
}
else
charCenter = '0';//set charCenter to '0' if it does not exist a center.(Actually there will be a problem if the real center is '0', I don't care LOL)
return sb;
}
public static void backtrack(char[] charArr, List<String> list, boolean[] visited, StringBuilder sb)
{
if(sb.length() == Len )
{
list.add(sb.toString()+(charCenter == '0'?"":charCenter)+sb.reverse().toString());
sb.reverse();//remeber to reverse sb back for further usage.
}
for(int i = 0 ; i < Len ; i++)
{
if(visited[i](i>0&&!visited[i1]&&charArr[i] == charArr[i1]))//this prevent you from dealing with the same letters which you have already dealt with. Key point is !visited[i1].
continue;
visited[i] = true;
sb.append(charArr[i]);
backtrack(charArr,list,visited,sb);// What a classic version of backtrack method!
visited[i] = false;//remember to "false" back
sb.deleteCharAt(sb.length()1);
}
}
}