Print all palindrome permutations of a string
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