# 267. Palindrome Permutation II

Reference: LeetCode
Difficulty: Medium

## 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:

Hint: If a palindromic permutation exists, we just need to generate the first half of the string.

## Analysis

### Brute-Force

The brute-force solution is based on the same idea in 266. Palindrome Permutation I. Since we have to deal with duplicate cases, we apply the approach of using a hash set skip considered elements.

Note:

Time: $O(N \times N!)$
Space: $O(N \times N!)$

### Backtracking

To construct a palindrome we build the first half, append the middle character (odd case), and concatenate the reversed string of the first half.

Before the permutation, we need to know what characters we need to construct the first half, and also find out what the middle character is if it exists. It could be done in the function checkAndConstruct of counting occurrences (see the code for details).

The idea is not difficult, but the implementation is.

Note: If the count is odd and greater than $1$, this character could both lie in the first half and the middle position, e.g. "ababa".

Helper class BuildInfo:

Main function:

Check palindromicity and construct BuildInfo for permuting.

Permutation:

Time: $O(N \times \frac{N}{2}!)$
Space: $O(N \times \frac{N}{2}!)$

Comment Junhao Wang
a software engineering cat