Palindrome Permutations of a String

Problem Statement

In the “Palindrome Permutations of a String” problem, we have given an input string “s”. Print all the possible palindromes that can be generated using the characters of the string.

Input Format

The first and only one line containing a string “s”.

Output Format

Print all the possible permutations line by line of the given string “s”.

Constraints

• 1<=|s|<=10
• s[i] must be a lower English alphabet

Example

aabbc

abcba
bacab

Algorithm

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

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

2. We will make half part of the string of the first palindrome string lexicographically smallest by taking half the 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 the string is of odd length, for making the palindrome.

Implementation

C++ Program for Palindrome Permutations of a String

#include <bits/stdc++.h> 
using namespace std; 
#define M 26 

bool isPalin(string str, int* freq) 
{
  memset(freq, 0, M * sizeof(int)); 
  int l = str.length(); 
  for (int i = 0; i < l; i++) 
    freq[str[i] - 'a']++; 

  int odd = 0; 
  for (int i = 0; i < M; i++) 
    if (freq[i] % 2 == 1) 
      odd++; 
  if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0)) 
    return true; 
  else
    return false; 
} 

string reverse(string str) 
{ 
  string rev = str; 
  reverse(rev.begin(), rev.end()); 
  return rev; 
} 

void printpalindromes(string str) 
{ 
  int freq[M]; 
  if (!isPalin(str, freq)) 
    return; 
  int l = str.length(); 
  string half = ""; 
  char oddC; 
  for (int i = 0; i < M; i++) 
  { 
    if(freq[i] % 2 == 1) 
      oddC = i + 'a'; 

    half += string(freq[i] / 2, i + 'a'); 
  } 
  string palin; 

  do
  { 
    palin = half; 
    if (l % 2 == 1) 
      palin += oddC; 
    palin += reverse(half); 
    cout << palin << endl; 
  } 
  while (next_permutation(half.begin(), half.end())); 
} 

int main() 
{ 
  string s;
  cin>>s;
  printpalindromes(s); 
  return 0; 
}

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static boolean isPalin(String str, int freq[]) 
    {
  for(int i=0;i<26;i++)
        {
            freq[i]=0;
        }
  int l = str.length(); 
  for (int i = 0; i < l; i++) 
    freq[str.charAt(i) - 'a']++; 

  int odd = 0; 
  for (int i = 0; i < 26; i++) 
    if (freq[i] % 2 == 1) 
      odd++; 
  if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0)) 
    return true; 
  else
    return false; 
    } 
    public static int isPalindrome(String s, int l, int h)  
    { 
        while(h > l) 
            if(s.charAt(l++) != s.charAt(h--)) 
                return 0; 
        return 1; 
    }
    static char[] swap(String str, int i, int j) 
    { 
        char ch[] = str.toCharArray(); 
        char temp = ch[i]; 
        ch[i] = ch[j]; 
        ch[j] = temp; 
        return ch; 
    }
    
    private static String next_permutation( final String c ) {
    int first = c.charAt(0);
    if ( first == -1 ) return null; 
                
    int toSwap = c.length()-1;
    while(c.charAt(first)>=( c.charAt(toSwap)))
      --toSwap;
    swap(c,first++,toSwap);
    toSwap = c.length() - 1;
    while ( first < toSwap )
      swap( c, first++, toSwap-- );
    return c;
  }
    public static void printpalindromes(String str) 
    { 
  int freq[] = new int[26]; 
  if(!isPalin(str, freq)) 
    return; 
  int l = str.length(); 
  String half = ""; 
        char oddC = 0;
  for(int i=0;i<26;i++) 
  { 
    if(freq[i]%2==1) 
      oddC = (char) (i + 'a'); 
                for(int q=0;q<freq[i]/2;q++)
                {
                    half+=(char) i+'a';
                }
  } 
  String palin;
  do
  { 
    palin = half; 
    if (l % 2 == 1) 
      palin += oddC; 
                StringBuilder x = new StringBuilder();
                x.append(half);
                x.reverse();
    palin +=x; 
    System.out.println(palin);
  } 
  while(next_permutation(half)!=null);
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
  printpalindromes(s);
    }
}

dababd

abddba
adbbda
baddab
bdaadb
dabbad
dbaabd

Complexity Analysis for Palindrome Permutations of a String

Time Complexity

O(n!) where n is denoting the length of the given string. Here we use next_permutation function which time complexity is n!.

Space Complexity

O(1) because we don’t use any auxiliary space here.