# Python solution sharing: Preprocess, then it would be like ordinary backtracking permutation!

• Take `aabbbcc` as an example

`counter` would be {"a":2, "b":3, "c":2}

After preprocess: `baseStr` = "abc", `mid` = "b" (if there is no char happens odd times, mid = "")

Then use backtracking to find all the permutation of `baseStr`,

the valid palindrome would be "permuStr + mid + reverseOfPermuStr"

``````def generatePalindromes(self, s):
counter = collections.Counter(s)
odds = filter(lambda x: x % 2, counter.values())
if len(odds) > 1:
return []
baseStr, mid = self.preProcess(counter)
return self.backTracking(baseStr, 0, mid, [baseStr + mid + baseStr[::-1]])

def preProcess(self, counter):
baseStr = mid = ""
for char in counter:
if counter[char] % 2:
mid = char
baseStr += char*(counter[char]/2)
return baseStr, mid

def backTracking(self, s, idx, mid, ans):
if idx == len(s) - 1:
return ans
for i in range(idx, len(s)):
if i >= 1 and s[i] == s[i-1] == s[idx]:
continue #no need to go deeper if swap would be the same
#Swap s[idx] with s[i]
if i != idx:
permu = s[:idx] + s[i] + s[idx+1:i] + s[idx] + s[i+1:]
ans.append(permu + mid + permu[::-1])
else:
permu = s
self.backTracking(permu, idx+1, mid, ans)
return ans``````

• not work for case "aaaabbbb"

• As your solution is not working in some cases, e.g. 'aaaabbbbcccc'. I modified it as following and it passed now. Thank you for sharing your idea.

``````class Solution(object):
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
# Get dictionary map char to its appearance
counter = collections.Counter(s)
mid, base, res = '', '', []
# Get mid char and base string
for c in counter:
if counter[c] % 2 != 0:
if mid: return []
else: mid = c
base += c * (counter[c] // 2)
# Start backtracking
self.backTracking(base, 0, mid, res)
return res

def backTracking(self, base, start, mid, res):
# No char to be permuted, which means reach out the leaf in the tree
if start == len(base):
res.append(base + mid + base[::-1])
return
# Loop to permute char @ start with itself and all following different char
for i in range(start, len(base)):
# Prune the branch as duplicated!!!
if i > start and (base[i] == base[i-1] or base[i] == base[start]):
continue
# Get the permutation
perm = base if i == start else base[:start] + base[i] + base[start+1:i] + base[start] + base[i+1:]
# Permute next char with following chars
self.backTracking(perm, start+1, mid, res)
``````

• This post is deleted!

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