• ㊗️
• 大家
• offer
• 多多！

## Problem

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]


Example 2:

Input: "abc"
Output: []


## Code

class Solution {
public List<String> generatePalindromes(String s) {
int[] dd = new int[26];

for(char c : s.toCharArray()) {
dd[c - 'a']++;
}

int odd = 0;
char oddC = 'a';

for(int i = 0; i < 26; i++) {
if(dd[i] % 2 == 1) {
odd++;
oddC = (char)('a' + i);
}
}

if(odd > 1){
return new ArrayList<>();
}

String base = "";
int ll = s.length();

if(odd == 1) {
base = oddC + "";
dd[oddC - 'a'] -= 1;
ll -= 1;
}

List<String> res = new ArrayList<>();
helper(res, base, dd, ll);
return res;
}

private void helper(List<String> res, String base, int[] dd, int ll) {
if(ll == 0){
return;
}

for(int i = 0; i < 26; i++) {
if(dd[i] == 0) continue;

dd[i] -= 2;
char c = (char)('a' + i);
helper(res, c + base + c, dd, ll - 2);
dd[i] += 2;
}

}
}

class Solution:
def helper(self, res: List[str], base: str, dd: {}, ll: int):
if ll == 0:
res.append(base)
return

for key in dd:
if dd[key] == 0:
continue
dd[key] -= 2
self.helper(res, key + base + key, dd, ll - 2)
dd[key] += 2

def generatePalindromes(self, s: str) -> List[str]:
dd = defaultdict(int)

for c in s:
dd[c] += 1

odd = 0
odd_c = ''
for key in dd:
if dd[key] % 2 == 1:
odd += 1
odd_c = key

if odd > 1:
return []

base = ""
ll = len(s)
if odd == 1:
base = odd_c
dd[odd_c] -= 1
ll -= 1

res = []
self.helper(res, base, dd, ll)
return res