Number of possible palindrome anagrams for a given word

Question

I have to find No. of palindrome anagrams are possible for a given word. Suppose the word is aaabbbb.My approach is

1. Prepare a hash map that contains no. of time each letter is appearing

   For my example it will be

   a--->3
   b--->4
   

   1. If length of string is even then no. of occurrence of each letter should be even to form palindrome of given word else no of palindrome anagrams is 0

   2. If length of string is odd then at max one occurrence of letter can be odd and other should be even.

This two above steps was for finding that weather a given word can can form palindrome or not.

Now for finding no of palindrome anagrams, what approach should I follow?

Answer 1

First thing to notice is that if the word is an odd length, then there must be exactly one character with an odd number of occurrences. If the word is an even length, then there must be no characters with an odd number of occurrences. In either case, you're looking for how many ways you can arrange the pairs of characters. You're looking for the number of permutations since order matters:

n = number of character pairs (aaaabbb would have 3 pairs, aabbcccc would have 4 pairs)

(n)!/( number_of_a_pairs! * number_of_b_pairs! * etc..)

So in the aaaabbb case, you're finding the permutations of aab:

3!/2!1! = 3

baa = baabaab

aba = abababa

aab = aabbbaa

And in the aabbcccc case, you're finding the permutations of abcc:

4!/2! = 12: abcc acbc accb bacc bcac bcca cabc cacb cbac cbca ccab ccba