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;
}
Try It

 


Next > < Prev
Scroll to Top