# Short backtracking solution in Java (3 ms)

• We only need to generate the first part of palindrome string, and the remaining part will be a middle character with the reverse of first part.

``````private List<String> list = new ArrayList<>();

public List<String> generatePalindromes(String s) {
int numOdds = 0; // How many characters that have odd number of count
int[] map = new int[256]; // Map from character to its frequency
for (char c: s.toCharArray()) {
map[c]++;
numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1;
}
if (numOdds > 1)   return list;

String mid = "";
int length = 0;
for (int i = 0; i < 256; i++) {
if (map[i] > 0) {
if ((map[i] & 1) == 1) { // Char with odd count will be in the middle
mid = "" + (char)i;
map[i]--;
}
map[i] /= 2; // Cut in half since we only generate half string
length += map[i]; // The length of half string
}
}
generatePalindromesHelper(map, length, "", mid);
return list;
}
private void generatePalindromesHelper(int[] map, int length, String s, String mid) {
if (s.length() == length) {
StringBuilder reverse = new StringBuilder(s).reverse(); // Second half
return;
}
for (int i = 0; i < 256; i++) { // backtracking just like permutation
if (map[i] > 0) {
map[i]--;
generatePalindromesHelper(map, length, s + (char)i, mid);
map[i]++;
}
}
}``````

• Hi lianngg, nice solution! Yet I found that the main speed gain comes from assuming that the chars are ascii. Otherwise the running time would be 11ms... what a difference.

• Same idea but improve a bit on the backtracking part.

``````public class Solution {
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<>();
int odd = 0;
String mid = "";
int []hash = new int[256];
int length = 0;
for(int i=0; i<s.length(); i++){
hash[s.charAt(i)]++;
}

for(int i=0; i<256; i++){
if(hash[i] > 0){
if(hash[i] % 2 != 0){
odd++;
if (odd > 1) return new LinkedList<String>();
mid = String.valueOf((char)i);
hash[i]--;
}
hash[i] /= 2;
length += hash[i];
}
}

backtrack(res, hash, new StringBuffer(), mid, length);
return res;
}

void backtrack(List<String> res, int[] hash, StringBuffer sb, String mid, int length){
if (sb.length() == length){
sb.reverse();
return;
}

for(int i=0; i<256; i++){
if(hash[i] > 0){
hash[i]--;
sb.append((char)i);
backtrack(res, hash, sb, mid, length);
sb.deleteCharAt(sb.length() -1);
hash[i]++;
}
}

}
}
``````

• numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1;

Nice trick!

• Nice solution!
One question here, why we don't need the duplicate check like we did for Permutation II here? How to ensure there is no duplicate string s?

for (int i = 0; i < 256; i++) { // backtracking just like permutation
if (map[i] > 0) {
map[i]--;
generatePalindromesHelper(map, length, s + (char)i, mid);
map[i]++;
}
}

• Wow that's a clear solution!
I think length can be got directly from "(s.length() - mid.length()) / 2" and don't need to count it in for loop

• @lianngg
One question here, why we don't need the duplicate check like we did for Permutation II here? How to ensure there is no duplicate string s?

• for (int i = 0; i < 256; i++) { // backtracking just like permutation
if (map[i] > 0) {
map[i]--;
generatePalindromesHelper(map, length, s + (char)i, mid);
map[i]++;
}
}

the total number of map[i] (i from 0 to 256) is fixed, so one element only used once, this avoids duplicate like [a,a,a] if the map indicates a string [a,c(1),c(2)]. Also in each stack of recursion this for loop goes from 0 to 255, and the map is updated each time, this avoids duplicates like [a, c(1), c(2)] and [a, c(2), c(1)].

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