Home » Technical Interview Questions » String Interview Questions » Palindrome permutations of a string

# Palindrome permutations of a string

## For the given input string, print all the possible palindromes that can be generated using characters of the string.

### Example

Input string : “aabbc
Output : abcba, bacab

## Algorithm

1. Check whether letters of string can make a palindrome or not, if it can`t form a palindrome return.

a. Initialize count array with zeroes.
b. Fill with the frequency with the count of characters.
c. If length is odd then only one character must contain odd count.
d. If length is even no letter should have odd frequency.

2. We will make half part of the string of first palindrome string lexicographically smallest by taking half frequency of each character of the input string.

3. Traverse through all possible permutation of the half string and each time add reverse of this part at the end.

4. add odd frequency character in mid between if string is of odd length, for making the palindrome.

## C++ Program

```#include <bits/stdc++.h>

using namespace std;
#define M 26

bool caNformPalindrome(string str, int* count_array)
{
//Initialize array with zeroes
for (int i = 0; i < 26; ++i)
{
count_array[i] = 0;
}
int length = str.length();

/* Updating frequency according to given string */
for (int i = 0; i < length; i++)
{
count_array[str[i] - 'a']++;
}
int odd_count = 0;
//Find odd_count
for (int i = 0; i < M; i++)
{
if (count_array[i] % 2 == 1)
{
odd_count++;
}
}
//if length is odd_count then only one letter's frequency must be odd_count
if ((length % 2 == 1 && odd_count == 1 ) || (length %2 == 0 && odd_count == 0))
{
return true;
}
else//if length is even no letter should have odd_count frequency
{
return false;
}
}
//Function to reverse the string
string reverse(string str)
{
string rev = str;
reverse(rev.begin(), rev.end());
return rev;
}

//Function to print
void printPalIndromes(string str)
{
int count_array[M];
// checking whether letter can make palindrome or not
if (!caNformPalindrome(str, count_array))
{
return;
}
int length = str.length();

// half will contain half part of all palindromes,
// that is why pushing half count_array of each letter
string half = "";
char mid;//store odd count charcter
for (int i = 0; i < M; i++)
{
if(count_array[i] % 2 == 1)
{
mid = i + 'a';
}
half += string(count_array[i] / 2, i + 'a');
}
string palindrome_string;
do
{
palindrome_string = half;
if (length % 2 == 1)
{
palindrome_string += mid;
}
palindrome_string += reverse(half);
cout<<palindrome_string<<endl;
}
while (next_permutation(half.begin(), half.end()));
}

//Main function
int main()
{
string str = "aacbb";
cout<<"Possible Permutations for Input_string "<<str<<" are: "<<endl;
printPalIndromes(str);
return 0;
}```