Clever Geek Handbook

The number of possible palindrome analogs for a given word

I need to find that it is possible to use palindrome analogs for a given word. Suppose the word aaabbbb

. My approach

  • Prepare a hash map that does not contain. time each letter appears

    In my example it would be

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

    • If the string length is equal, then no. the appearance of each letter must be even for the formation of the palindrome of the given word, otherwise there are no panamronic anagrams 0

    • If the length of the string is odd, then at max one occurrence of the letter can be odd, and the other must be even.

These two aforementioned steps were in order to find out what weather, a given word, can form a palindrome or not.

Now, in order not to find an analogue of the palindrome, which approach should be followed?

+3


source to share


1 answer


First of all, it should be noted that if the word is of odd length, then there must be exactly one character with an odd number of occurrences. If the word is of even length, then there must be no characters with an odd number of occurrences. You are looking for how many ways to organize pairs of symbols anyway. You are looking for the number of permutations starting from order:

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

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

So, in the case of aaaabbb, you find the permutations of aab:

3! / 2! 1! = 3



baa = baabaab

aba = abababa

aab = aabbbaa

And in the case of aabbcccc, you find the abcc permutations:

4! / 2! = 12: CCA acbc ACCB bacc BCAC BCCA CABC CACB CBAC CBCA CCAB CCBA

+5


source






More articles:


All Articles