Find all palindromic permutations of a string

Given a string, find all palindromic permutations of it.

 

For example,


Input:

str = xyxzwxxyz

Output:

xxyzwzyxx
xxzywyzxx
xyxzwzxyx
xyzxwxzyx
xzxywyxzx
xzyxwxyzx
yxxzwzxxy
yxzxwxzxy
yzxxwxxzy
zxxywyxxz
zxyxwxyxz
zyxxwxxyz

 

 
We know that the left and right half of a palindrome contains same set of characters, so any palindromic permutations of a string is only possible if the frequency of each character in the string is even. Also, for odd length palindromic permutations, only one occurrence of an odd occurring number is allowed. The odd character will form mid character of all such palindromic permutations.

We can use above observation to solve given problem. The idea is to find the characters involved in left half any palindromic permutation and construct a string containing all such characters. All characters involved in the left half have even frequencies. For any character with even frequency, half of the characters will go in left half of the palindrome and the other half will go in its right half. After we construct the string, we sort it to generate permutations in lexicographical order using std::next_permutation or std::prev_permutation depending upon the string is sorted in ascending or descending order. Now for each permutation of the string (which will forms left half of palindrome), we can easily construct the right half by reversing the left half. If the string contains one odd occurring element, all palindromic permutations will be of odd length with mid element equal to odd occurring character. As mentioned earlier, no solution is possible if the string contains more than one odd occurring element.

 
C++ implementation –
 

Download   Run Code

Output:

xxyzwzyxx
xxzywyzxx
xyxzwzxyx
xyzxwxzyx
xzxywyxzx
xzyxwxyzx
yxxzwzxxy
yxzxwxzxy
yzxxwxxzy
zxxywyxxz
zxyxwxyxz
zyxxwxxyz

 

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Noe
Guest

An implementation in Java :