# AC Java solution with explanation

• Basically, the idea is to perform permutation on half of the palindromic string and then form the full palindromic result.

``````public List<String> generatePalindromes(String s) {
int odd = 0;
String mid = "";
List<String> res = new ArrayList<>();
List<Character> list = new ArrayList<>();
Map<Character, Integer> map = new HashMap<>();

// step 1. build character count map and count odds
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
odd += map.get(c) % 2 != 0 ? 1 : -1;
}

// cannot form any palindromic string
if (odd > 1) return res;

// step 2. add half count of each character to list
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
char key = entry.getKey();
int val = entry.getValue();

if (val % 2 != 0) mid += key;

for (int i = 0; i < val / 2; i++) list.add(key);
}

// step 3. generate all the permutations
getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);

return res;
}

// generate all unique permutation from list
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == list.size()) {
// form the palindromic string
res.add(sb.toString() + mid + sb.reverse().toString());
sb.reverse();
return;
}

for (int i = 0; i < list.size(); i++) {
// avoid duplication
if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;

if (!used[i]) {
used[i] = true; sb.append(list.get(i));
// recursion
getPerm(list, mid, used, sb, res);
// backtracking
used[i] = false; sb.deleteCharAt(sb.length() - 1);
}
}
}``````

• Nice and straightforward. Thanks a lot!

• Good idea to carry around half of the string, and populate the other half when necessary.

• Why do you need to call "sb.reverse()" once you find a solution?

• sb is reversed first time here: res.add(sb.toString() + mid + sb.reverse().toString());
To restore the original sequence, you have to reverse back

• Hi @jeantimex, I have a little confusion about the duplicates avoidance, how do you use used[] to avoid duplicates. Could you please explain the following line?

``````if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;
``````

Thank you!

• @jeantimex, please ignore the previous comment I left, I have understood it, that is really awesome! I used to use a hash set to avoid duplicates when the whole string built, but with the used[], we can avoid it in the at a very early time. Thank you for your solution.

• I got a quick question. For the permutation II, we need to sort the array in order to avoid the duplicates. And for you solution, you did not sort the list. Can anyone tell me why it is still working?

• @zws1818918 In permutation II, we sort the list because we just want to make sure that same elements can be located at adjacent positions, and here when we iterate the map, we already put the same elements together. Therefore, we don't need to sort the list here since the general order doesn't matter.

• @zws1818918 Because when we add the key into the list in step 2, we add the keys from the same entry until there's no more key in the same entry. So the keys added in list already has the duplicate keys together. Thus we don't need to sort the list again later.

• Can some1 explain to me how mid works. e.g 'bacb'

• @jeantimex I'm not pretty sure if mine is correct. Thanks in advance if you or someone else could do me a favor to confirm.

``````    public List<String> generatePalindromes(String str) {
int[] dict = new int[256];
for (char c : str.toCharArray())
dict[c]++;

List<String> ret = new ArrayList<>();
String odd = null;
for (int i = 0; i < dict.length; i++) { // If there is single char, then it must be in middle
if (dict[i] == 1) {
if (odd == null) odd = String.valueOf((char) i);
else return ret;
}
}
generate(ret, (odd == null) ? "" : odd, dict, str.length());
return ret;
}

private void generate(List<String> ret, String path, int[] dict, int max) {
if (path.length() == max) {
ret.add(path);
return;
}

for (int i = 0; i < dict.length; i++) {
if (dict[i] >= 2) { // Only use once for same character
dict[i] -= 2;
generate(ret, (char) i + path + (char) i, dict, max);
dict[i] += 2;
}
}
}
``````

I just tried to follow the common template for combinatrial problem to traverse the tree of search space.

• I think time complexity is, O(n^n), n=s.length()/2

• I believe this is much Simpler Implementation.

``````   public List<String> generatePalindromes(String s) {
List<String> ans = new ArrayList<>();
int [] count = new int [256]; int odds = 0;
for (char c : s.toCharArray()) count [c] ++;
for (int c : count) if (c % 2 != 0) odds ++;
if (odds <= 1) {
Character center = null;
for (int idx = 0; idx < count.length; idx ++)
if (count [idx] % 2 == 1) {
center = ((char) idx);
count [idx] --;
break;
}

generate (ans, count, (center != null ? String.valueOf(center) : new String ()), s.length());
}
return ans;
}

private void generate (List<String> ans, int[] count, String build, int len) {
for (int idx = 0; idx < count.length; idx ++) {
if (count [idx] > 0) {
count [idx] -= 2;
generate (ans, count, ((char) idx) + build + ((char) idx), len);
count [idx] += 2;
}
}
if (build.length() == len) ans.add (new String (build));
}
``````

• I have the similar idea, but I have problem is what the time complexity of it?

``````public class Solution {
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<String>();
// corner case
if (s == null && s.length() == 0) {
res.add("");
return res;
}
// use hashMap
HashMap<Character, Integer> map = new HashMap<>();
char[] c = s.toCharArray();
for (char i : c) {
if (!map.containsKey(i)) map.put(i, 1);
else map.put(i, map.get(i) + 1);
}
// determine
int count = 0;
boolean isV = true;
char oddc = 'a';
for (char cc: map.keySet()) {
if (map.get(cc) % 2 == 1) {
oddc = cc;
count++;
}
if (count > 1) isV = false;
}
if (!isV) return res;
// now the num can be P
List<Character> list = new ArrayList<>(map.keySet());
if (s.length() % 2 == 1) {
map.put(oddc, map.get(oddc) - 1);
if (map.get(oddc) == 0) map.remove(oddc);
dfs(res, "" + oddc, map, s.length(), list);
} else {
dfs(res, "", map, s.length(), list);
}
return res;
}
private void dfs(List<String> res, String s, HashMap<Character, Integer> map, int len, List<Character> mem) {
if (s.length() == len) {
if (!res.contains(s)) res.add(s);
return;
}
for (char c: mem) {
if (!map.containsKey(c)) continue;
map.put(c,map.get(c) - 2);
if(map.get(c) == 0) map.remove(c);
dfs(res, c + s + c, map, len, mem);
map.put(c, map.getOrDefault(c, 0) + 2);
}
}
}
``````

• I really like the way you deal with duplicates: if there are duplicates, use the first one of unused or skip it.

• This post is deleted!

• To who are confused with the way @jeantimex deal with duplicates,

``````if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;
``````

here is a simple explanation: think about the following string `baaaccd`,

``````            skip the following 3 characters
|  |     |
[b, a, a, a, c, c, d]
``````

When we have tried the permutation begin with `ba`, we don't want to try another `ba`, so just skip the following 2 `a`, and build the permutation from `bc`.

The same thing happens when we meet the 2nd `c`.

• Another hint, although the `Backtracking` works well for this problem. We can also use `Dynamic Programming` to solve `Permutation`.

``````    /* Dynamic Programming */
private Set<String> permutation(String letters) {
Set<String> result = new HashSet<>();
if (letters.length() == 0) { return result; }
if (letters.length() == 1) { result.add(letters); return result ; }
char c = letters.charAt(0);
Set<String> subSet = permutation(letters.substring(1));
for (String str : subSet) {
int len = str.length();
for (int i = 0; i <= len; i++) {
result.add(str.substring(0,i) + c + str.substring(i,len));
}
}
return result;
}
``````

• Share my simple and elegant solution here.

``````from collections import Counter
class Solution(object):
def generatePalindromes(self, s):
counts = Counter(s)
odd = ''
for ch in counts:
if counts[ch] % 2 == 1:
if odd != '':
return []
odd = ch
counts[ch] /= 2

perms = self.get_permutations(counts)
return map(lambda word: word + odd + word[::-1], perms)

def get_permutations(self, counts):
strs = []
def helper(s):
if counts.most_common(1)[0][1] == 0:
strs.append(s)
return
'''
This works because the for loop count unique character only.
Each time you consider a character the count itself is like an index of the duplicated number.
This implies that the 'a' with count (index) 8, will never occur after another 'a' with count (index) 6.
'''
for ch in counts:
if counts[ch] == 0:
continue
counts[ch] -= 1
helper(s + ch)
counts[ch] += 1
helper('')
return strs
``````

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