Number of palindromic permutations | Set 1 | CPP program to find number of palindromic permutations of a given string ; Returns factorial of n ; Returns count of palindromic permutations of str . ; Count frequencies of all characters ; Since half of the characters decide count of palindromic permutations , we take ( n / 2 ) ! ; To make sure that there is at most one odd occurring char ; Traverse through all counts ; To make sure that the string can permute to form a palindrome ; If there are more than one odd occurring chars ; Divide all permutations with repeated characters ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 256 ; long long int fact ( int n ) { long long int res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = res * i ; return res ; } int countPalinPermutations ( string & str ) { int n = str . length ( ) ; int freq [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) freq [ str [ i ] ] ++ ; long long int res = fact ( n / 2 ) ; bool oddFreq = false ; for ( int i = 0 ; i < MAX ; i ++ ) { int half = freq [ i ] / 2 ; if ( freq [ i ] % 2 != 0 ) { if ( oddFreq == true ) return 0 ; oddFreq = true ; } res = res / fact ( half ) ; } return res ; } int main ( ) { string str = " gffg " ; cout << countPalinPermutations ( str ) ; return 0 ; }