## Palindrome Permutation II

• Time:O(n^n)
• Space:O(|\texttt{ans}|)

## C++

``````class Solution {
public:
vector<string> generatePalindromes(string s) {
int odd = 0;
unordered_map<char, int> count;

// get character occurrence
for (const char c : s)
++count[c];

// count odd one
for (const auto& [_, value] : count)
if (value & 1)
++odd;

// can't form any palindrome
if (odd > 1)
return {};

vector<string> ans;
vector<char> candidates;
string mid;

// get mid and candidates characters
for (const auto& [key, value] : count) {
if (value & 1)
mid += key;
for (int i = 0; i < value / 2; ++i)
candidates.push_back(key);
}

// backtracking to generate our ans (strings)
dfs(candidates, mid, vector<bool>(candidates.size()), "", ans);
return ans;
}

private:
// generate all unique palindromes from candidates
void dfs(const vector<char>& candidates, const string& mid,
vector<bool>&& used, string&& path, vector<string>& ans) {
if (path.length() == candidates.size()) {
string secondHalf = path;
reverse(begin(secondHalf), end(secondHalf));
ans.push_back(path + mid + secondHalf);
return;
}

for (int i = 0; i < candidates.size(); ++i) {
if (used[i])
continue;
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])
continue;
used[i] = true;
path.push_back(candidates[i]);
dfs(candidates, mid, move(used), move(path), ans);
path.pop_back();
used[i] = false;
}
}
};
``````

## JAVA

``````class Solution {
public List<String> generatePalindromes(String s) {
int odd = 0;
Map<Character, Integer> count = new HashMap<>();

// get character occurrence
for (final char c : s.toCharArray())
count.put(c, count.getOrDefault(c, 0) + 1);

// count odd one
for (Map.Entry<Character, Integer> entry : count.entrySet())
if (entry.getValue() % 2 == 1)
++odd;

// can't form any palindrome
if (odd > 1)
return new ArrayList<>();

List<String> ans = new ArrayList<>();
List<Character> candidates = new ArrayList<>();
StringBuilder mid = new StringBuilder();

// get mid and candidates characters
for (Map.Entry<Character, Integer> entry : count.entrySet()) {
final char key = entry.getKey();
final int value = entry.getValue();
if (value % 2 == 1)
mid.append(key);
for (int i = 0; i < value / 2; ++i)
}

// backtracking to generate our ans (strings)
dfs(candidates, mid, new boolean[candidates.size()], new StringBuilder(), ans);
return ans;
}

// generate all unique palindromes from candidates
private void dfs(List<Character> candidates, StringBuilder mid, boolean[] used, StringBuilder sb,
List<String> ans) {
if (sb.length() == candidates.size()) {
sb.reverse();
return;
}

for (int i = 0; i < candidates.size(); ++i) {
if (used[i])
continue;
if (i > 0 && candidates.get(i) == candidates.get(i - 1) && !used[i - 1])
continue;
used[i] = true;
sb.append(candidates.get(i));
dfs(candidates, mid, used, sb, ans);
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
``````

## Python

``````class Solution:
def generatePalindromes(self, s: str) -> List[str]:
# get character occurrence
count = Counter(s)

# count odd one
odd = sum(value & 1 for value in count.values())

# can't form any palindrome
if odd > 1:
return []

ans = []
candidates = []
mid = ''

# get mid and candidates characters
for key, value in count.items():
if value & 1:
mid += key
for _ in range(value // 2):
candidates.append(key)

# generate all unique palindromes from candidates
def dfs(used: List[bool], path: List[chr]) -> None:
if len(path) == len(candidates):
ans.append(''.join(path) + mid + ''.join(path[::-1]))
return

for i, candidate in enumerate(candidates):
if used[i]:
continue
if i > 0 and candidate == candidates[i - 1] and not used[i - 1]:
continue
used[i] = True
path.append(candidate)
dfs(used, path)
path.pop()
used[i] = False

# backtracking to generate our ans (strings)
dfs([False] * len(candidates), [])
return ans
``````