Print all palindrome permutations of a string

Last Updated : 25 Apr, 2023

Given a string, we need to print all possible palindromes that can be generated using letters of that string. Examples:

Input:  str = "aabcb"
Output: abcba bacab

Input:  str = "aabbcadad"
Output: aabdcdbaa aadbcbdaa abadcdaba
        abdacadba adabcbada adbacabda
        baadcdaab badacadab bdaacaadb
        daabcbaad dabacabad dbaacaabd

Generation of palindrome can be done by following steps,

First we need to check whether letters of string can make a palindrome or not, if not then return.
After above checking we can make half part of first palindrome string (lexicographically smallest) by taking half frequency of each letter of the given string.
Now traverse through all possible permutation of this half string and each time add reverse of this part at the end and add odd frequency character in mid between if string is of odd length, for making the palindrome.

Below is C++ implementation.

C++

// C++ program to print all palindrome permutations of
// a string.
#include <bits/stdc++.h>
using namespace std;
#define M 26
 
/* Utility function to count frequencies and checking
    whether letter can make a palindrome or not */
bool isPalin(string str, int* freq)
{
    /* Initialising frequency array with all zeros */
    memset(freq, 0, M * sizeof(int));
    int l = str.length();
 
    /* Updating frequency according to given string */
    for (int i = 0; i < l; i++)
        freq[str[i] - 'a']++;
 
    int odd = 0;
 
    /* Loop to count total letter with odd frequency */
    for (int i = 0; i < M; i++)
        if (freq[i] % 2 == 1)
            odd++;
 
    /* Palindrome condition :
    if length is odd then only one letter's frequency must be odd
    if length is even no letter should have odd frequency */
    if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
        return true;
    else
        return false;
}
 
/* Utility function to reverse a string */
string reverse(string str)
{
    string rev = str;
    reverse(rev.begin(), rev.end());
    return rev;
}
 
/* Function to print all possible palindromes by letter of
    given string */
void printAllPossiblePalindromes(string str)
{
    int freq[M];
 
    // checking whether letter can make palindrome or not
    if (!isPalin(str, freq))
        return;
 
    int l = str.length();
 
    // half will contain half part of all palindromes,
    // that is why pushing half freq of each letter
    string half = "";
    char oddC;
    for (int i = 0; i < M; i++)
    {
        /* This condition will be true at most once */
        if(freq[i] % 2 == 1)
            oddC = i + 'a';
 
        half += string(freq[i] / 2, i + 'a');
    }
 
    /* palin will store the possible palindromes one by one */
    string palin;
 
    // Now looping through all permutation of half, and adding
    // reverse part at end.
    // if length is odd, then pushing oddCharacter also in mid
    do
    {
        palin = half;
        if (l % 2 == 1)
            palin += oddC;
        palin += reverse(half);
        cout << palin << endl;
    }
    while (next_permutation(half.begin(), half.end()));
}
 
// Driver Program to test above function
int main()
{
    string str = "aabbcadad";
    cout << "All palindrome permutations of " << str << endl;
    printAllPossiblePalindromes(str);
    return 0;
}

Python3

from collections import defaultdict
from itertools import permutations
 
# Utility function to count frequencies and checking whether letter can make a palindrome or not
def isPalin(s, freq):
    # Initialising frequency array with all zeros
    freq.clear()
    for i in range(26):
        freq[chr(ord('a')+i)] = 0
    l = len(s)
 
    # Updating frequency according to given string
    for i in range(l):
        freq[s[i]] += 1
 
    odd = 0
 
    # Loop to count total letter with odd frequency
    for i in range(26):
        if freq[chr(ord('a')+i)] % 2 == 1:
            odd += 1
 
    # Palindrome condition :
    # if length is odd then only one letter's frequency must be odd
    # if length is even no letter should have odd frequency
    return (l % 2 == 1 and odd == 1) or (l % 2 == 0 and odd == 0)
 
# Utility function to reverse a string
def reverse(s:str)->str:
    return s[::-1]
 
# Function to print all possible palindromes by letter of given string
def printAllPossiblePalindromes(s:str)->None:
    freq = defaultdict(int)
 
    # checking whether letter can make palindrome or not
    if not isPalin(s, freq):
        return
 
    l = len(s)
 
    # half will contain half part of all palindromes,
    # that is why pushing half freq of each letter
    half = ""
    oddC = ''
    for i in range(26):
        if freq[chr(ord('a')+i)] % 2 == 1:
            oddC = chr(ord('a')+i)
        half += freq[chr(ord('a')+i)] // 2 * chr(ord('a')+i)
 
    # palin will store the possible palindromes one by one
    palin = ""
 
    # Now looping through all permutation of half, and adding
    # reverse part at end.
    # if length is odd, then pushing oddCharacter also in mid
    xd=set()
    for p in permutations(half):
        palin = ''.join(p)
        if l % 2 == 1:
            palin += oddC
        palin += reverse(''.join(p))
        if palin not in xd:
          print(palin)
          xd.add(palin)
 
# Driver Program to test above function
if __name__ == "__main__":
    s = "aabbcadad"
    print(f"All palindrome permutations of {s}")
    printAllPossiblePalindromes(s)

C#

using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
   
  // Function to check whether a string can make
  // a palindrome or not by checking letter frequencies
  public static bool IsPalin(string s,
                             Dictionary<char, int> freq)
  {
    freq.Clear(); // Clear frequency map
    // Initialize frequency map to all zeros
    for (int i = 0; i < 26; i++) {
      freq[(char)('a' + i)] = 0;
    }
    int l = s.Length;
     
    // Update frequency map according to given string
    for (int i = 0; i < l; i++) {
      freq[s[i]] += 1;
    }
    int odd = 0;
     
    // Loop to count total letters with odd frequency
    for (int i = 0; i < 26; i++) {
      if (freq[(char)('a' + i)] % 2 == 1) {
        odd += 1;
      }
    }
     
    // Palindrome condition :
    // if length is odd then only one letter's frequency
    // must be odd if length is even no letter should
    // have odd frequency
    return (l % 2 == 1 && odd == 1)
      || (l % 2 == 0 && odd == 0);
  }
 
  // Function to reverse a string
  public static string Reverse(string s)
  {
    char[] arr = s.ToCharArray();
    Array.Reverse(arr);
    return new string(arr);
  }
 
  // Function to print all possible palindromes by letter
  // of given string
  public static void PrintAllPossiblePalindromes(string s)
  {
    Dictionary<char, int> freq
      = new Dictionary<char, int>();
     
    // Checking whether the input string can make a
    // palindrome or not
    if (!IsPalin(s, freq)) {
      return;
    }
    int l = s.Length;
    string half = "";
    char oddC = '\0';
     
    // Create a string with half of the letters of the
    // palindrome and keep track of the letter with an
    // odd frequency (if any)
    for (int i = 0; i < 26; i++) {
      if (freq[(char)('a' + i)] % 2 == 1) {
        oddC = (char)('a' + i);
      }
      half += new string(
        (char)('a' + i),
        (int)((int)freq[(char)('a' + i)] / 2));
    }
    string palin = "";
    HashSet<string> xd = new HashSet<string>();
     
    // Loop through all permutations of half and add the
    // reverse of the permutation to the end If the
    // length is odd, add the odd letter in the middle
    // as well
    foreach(var p in Permuate(half.ToCharArray()))
    {
      palin = new string(p);
      if (l % 2 == 1) {
        palin += oddC;
      }
      palin += Reverse(new string(p));
       
      // Add unique palindrome to the set and print it
      if (!xd.Contains(palin)) {
        Console.WriteLine(palin);
        xd.Add(palin);
      }
    }
  }
 
  // Function to generate all permutations of an array
  public static List<char[]> Permuate(char[] arr)
  {
    List<char[]> result = new List<char[]>();
    if (arr.Length == 1) {
      result.Add(arr);
    }
    else {
      for (int i = 0; i < arr.Length; i++) {
        char current = arr[i];
        char[] remaining
          = arr.Take(i)
          .Concat(arr.Skip(i + 1))
          .ToArray();
        List<char[]> remainingPermuted
          = Permuate(remaining);
 
        for (int j = 0; j < remainingPermuted.Count;
             j++) {
          char[] temp = new char
            [1 + remainingPermuted[j].Length];
          temp[0] = current;
          for (int k = 0;
               k < remainingPermuted[j].Length;
               k++)
            temp[k + 1]
            = remainingPermuted[j][k];
          result.Add(temp);
        }
      }
    }
    return result;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    string s = "aabbcadad";
    Console.WriteLine("All palindrome permutations of "
                      + s);
 
    // Function call
    PrintAllPossiblePalindromes(s);
  }
}

Javascript

// Function to check whether a string can make 
// a palindrome or not by checking letter frequencies
function isPalin(s, freq) {
freq.clear(); // Clear frequency map
// Initialize frequency map to all zeros
for (let i = 0; i < 26; i++) {
freq[String.fromCharCode('a'.charCodeAt(0) + i)] = 0;
}
const l = s.length;
// Update frequency map according to given string
for (let i = 0; i < l; i++) {
freq[s[i]] += 1;
}
let odd = 0;
// Loop to count total letters with odd frequency
for (let i = 0; i < 26; i++) {
if (freq[String.fromCharCode('a'.charCodeAt(0) + i)] % 2 === 1) {
odd += 1;
}
}
// Palindrome condition :
// if length is odd then only one letter's frequency must be odd
// if length is even no letter should have odd frequency
return (l % 2 === 1 && odd === 1) || (l % 2 === 0 && odd === 0);
}
 
// Function to reverse a string
function reverse(s) {
return s.split("").reverse().join("");
}
 
// Function to print all possible palindromes by letter of given string
function printAllPossiblePalindromes(s) {
const freq = new Map();
// Checking whether the input string can make a palindrome or not
if (!isPalin(s, freq)) {
return;
}
const l = s.length;
let half = "";
let oddC = '';
// Create a string with half of the letters of the palindrome
// and keep track of the letter with an odd frequency (if any)
for (let i = 0; i < 26; i++) {
if (freq[String.fromCharCode('a'.charCodeAt(0) + i)] % 2 === 1) {
oddC = String.fromCharCode('a'.charCodeAt(0) + i);
}
half += String.fromCharCode('a'.charCodeAt(0) + i).repeat(Math.floor(freq[String.fromCharCode('a'.charCodeAt(0) + i)] / 2));
}
let palin = "";
const xd = new Set();
// Loop through all permutations of half and add the reverse of the permutation to the end
// If the length is odd, add the odd letter in the middle as well
for (let p of permute(half.split(""))) {
palin = p.join("");
if (l % 2 === 1) {
palin += oddC;
}
palin += reverse(p.join(""));
// Add unique palindrome to the set and print it
if (!xd.has(palin)) {
console.log(palin);
xd.add(palin);
}
}
}
 
// Function to generate all permutations of an array
function permute(arr) {
if (arr.length === 1) {
return [arr];
}
const result = [];
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
const remainingPermuted = permute(remaining);
for (let j = 0; j < remainingPermuted.length; j++) {
result.push([current].concat(remainingPermuted[j]));
}
}
return result}
 
const s = "aabbcadad";
console.log(`All palindrome permutations of ${s}`);
printAllPossiblePalindromes(s);

Java

import java.util.*;
 
public class GFG {
    public static boolean isPalin(String s,
                                   HashMap<Character, Integer> freq) {
        freq.clear();
        for (int i = 0; i < 26; i++) {
            freq.put((char)('a' + i), 0);
        }
        int l = s.length();
         
         // Update frequency map according to given string
        for (int i = 0; i < l; i++) {
            freq.put(s.charAt(i), freq.get(s.charAt(i)) + 1);
        }
        int odd = 0;
         
        // Loop to count total letters with odd frequency
        for (int i = 0; i < 26; i++) {
            if (freq.get((char)('a' + i)) % 2 == 1) {
                odd += 1;
            }
        }
         
     
    // Palindrome condition :
    // if length is odd then only one letter's frequency
    // must be odd if length is even no letter should
    // have odd frequency
        return (l % 2 == 1 && odd == 1)
            || (l % 2 == 0 && odd == 0);
    }
 
 // Function to reverse a string
    public static String reverse(String s) {
        char[] arr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            sb.append(arr[i]);
        }
         
        return sb.toString();
    }
 
  // Function to print all possible palindromes by letter
  // of given string
    public static void printAllPossiblePalindromes(String s) {
        HashMap<Character, Integer> freq
            = new HashMap<Character, Integer>();
         
    // Checking whether the input string can make a
    // palindrome or not
        if (!isPalin(s, freq)) {
            return;
        }
        int l = s.length();
        String half = "";
        char oddC = '\0';
         
         
    // Create a string with half of the letters of the
    // palindrome and keep track of the letter with an
    // odd frequency (if any)
        for (int i = 0; i < 26; i++) {
            if (freq.get((char)('a' + i)) % 2 == 1) {
                oddC = (char)('a' + i);
            }
            half += new String(
                new char[(int)(freq.get((char)('a' + i)) / 2)])
                    .replace('\0', (char)('a' + i));
        }
        String palin = "";
        HashSet<String> xd = new HashSet<String>();
          
    // Loop through all permutations of half and add the
    // reverse of the permutation to the end If the
    // length is odd, add the odd letter in the middle
    // as well
        for (char[] p : permute(half.toCharArray())) {
            palin = new String(p);
            if (l % 2 == 1) {
                palin += oddC;
            }
            palin += reverse(new String(p));
            if (!xd.contains(palin)) {
                System.out.println(palin);
                xd.add(palin);
            }
        }
    }
 
// Function to generate all permutations of an array
    public static List<char[]> permute(char[] arr) {
        List<char[]> result = new ArrayList<char[]>();
        if (arr.length == 1) {
            result.add(arr);
        } else {
            for (int i = 0; i < arr.length; i++) {
                char current = arr[i];
                char[] remaining = new char[arr.length - 1];
                int index = 0;
                for (int j = 0; j < arr.length; j++) {
                    if (j != i) {
                        remaining[index++] = arr[j];
                    }
                }
                List<char[]> remainingPermuted = permute(remaining);
                for (int j = 0; j < remainingPermuted.size(); j++) {
                    char[] temp = new char[1 + remainingPermuted.get(j).length];
                    temp[0] = current;
                    for (int k = 0; k < remainingPermuted.get(j).length; k++) {
                                        temp[k + 1] = remainingPermuted.get(j)[k];
                }
                result.add(temp);
            }
        }
    }
    return result;
}
 
// Driver code
public static void main(String[] args) {
    String s = "aabbcadad";
    System.out.println("All palindrome permutations of "+ s);
 
    // Function call
    printAllPossiblePalindromes(s);
}
}

Output

All palindrome permutations of aabbcadad
aabdcdbaa
aadbcbdaa
abadcdaba
abdacadba
adabcbada
adbacabda
baadcdaab
badacadab
bdaacaadb
daabcbaad
dabacabad
dbaacaabd

Time Complexity: O((n/2)!), where n is the length of string and we are finding all possible permutations of half of it.
Auxiliary Space: O(1)

Illustration :

Let given string is "aabbcadad"

Letters have following frequencies : 
 a(4), b(2), c(1), d(2).

As all letter has even frequency except one we can 
make palindromes with the letter of this string.

Now half part is – aabd

So traversing through all possible permutations of 
this half string and adding odd frequency character 
and reverse of string at the end we get following 
possible palindrome as final result : 
aabdcdbaa   aadbcbdaa   abadcdaba   abdacadba
adabcbada   adbacabda   baadcdaab   badacadab
bdaacaadb   daabcbaad   dabacabad   dbaacaabd

Suggest improvement

Count of Palindromic substrings in an Index range

Largest palindromic number by permuting digits

Share your thoughts in the comments

Check Palindrome by Different Language

Easy Problems on Palindrome

Medium Problems on Palindrome

Hard Problems on Palindrome