Print all palindrome permutations of a string - GeeksforGeeks
Given a string, we need to print all possible palindromes that can be generated using letters of that string.
http://code.geeksforgeeks.org/ASKfdd
Read full article from Print all palindrome permutations of a string - GeeksforGeeks
Given a string, we need to print all possible palindromes that can be generated using letters of that string.
Input: str = "aabbcadad" Output: aabdcdbaa aadbcbdaa abadcdaba abdacadba adabcbada adbacabda baadcdaab badacadab bdaacaadb daabcbaad dabacabad dbaacaabd
- 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.
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()));
}
Read full article from Print all palindrome permutations of a string - GeeksforGeeks