**Solution**

**Palindrome Permutation II** https://leetcode.com/problems/palindrome-permutation-ii/

**Simple Backtracking**

- Palindrome can have at-most one odd character.
- We use this fact to test if we can form palindromes or not. We build a frequency map. If we determine we can build palindromes, then we adjust (decrease by 1) the frequency of the single odd frequency character if there is any.
- We create a so_far array and if there is an odd frequency character, we place it in the middle.
- Recursion uses s, e to indicate the start and end of so_far. We iterate the counter and pick the character with non-zero frequency. We place the character and increment/decrement s and e.

```
from collections import Counter
class Solution(object):
def helper(self, s, e, ctr, so_far, result):
if s >= e:
result.append("".join(so_far))
else:
for k in ctr:
if ctr[k] > 0:
sp, ep = so_far[s], so_far[e]
so_far[s], so_far[e] = k, k
ctr[k] -= 2
self.helper(s+1, e-1, ctr, so_far, result)
ctr[k] += 2
so_far[s], so_far[e] = sp, ep
return
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
# Build a counter map.
ctr = Counter(s)
# Test if the string can form a palindrome or not
if bool(sum(map(lambda x: x&1, ctr.values())) > 1):
return []
odd_ch, so_far = None, [None]*len(s)
# Find the odd valued character
for k,v in ctr.items():
if v & 1:
odd_ch = k
# Decrement frequency of odd valued character by 1.
# Place it in center of so_far array
if odd_ch:
ctr[odd_ch], so_far[len(s)//2] = ctr[odd_ch]-1, odd_ch
result = []
self.helper(0, len(s)-1, ctr, so_far, result)
return result
```

**Another Approach**

- If a palindromic permutation exists, we just need to generate the first half of the string.
- Use the idea from:https://leetcode.com/problems/permutations-ii/