```
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return []
s_count = collections.Counter(s)
odd_char = None
half_s = ''
for c, freq in s_count.items():
if freq%2 == 1:
if odd_char:
return []
odd_char = c
half_s += c * (freq//2)
half_perm = []
self.dfs(half_s, '', half_perm)
res = []
if odd_char is None:
for half in half_perm:
res.append(half + half[::-1])
else:
for half in half_perm:
res.append(half + odd_char + half[::-1])
return res
def dfs(self, s, path ,res):
if not s:
res.append(path)
for i in range(len(s)):
if i > 0 and s[i] == s[i-1]:
continue
self.dfs(s[:i] + s[i+1:], path + s[i], res)
```