Search code examples
c++stringalgorithmpalindromeanagram

what's number anagram which are palindromes in string

What is the number of anagrams which are palindromes in a string? Example : string = "aaabbbb"; Possible anagram's which are palindromes "abbabba" , "bbaaabb" and "bababab". The problem here is the time, i have string of size 10^9. here's my final code can anybody tell me what's the wrong with it ?

Solution

  • Every letter in your input string has to appear in an even amount, execpt one letter can appear in an odd amount. This letter has a fixed position in the palindron. It has to be exactly in the middle. Lets say the amounts of the letter a,b,c,... are #a, #b, #c, ...

    You only care about half of those letters, because in an palindron, the second half depands of the first half. So we only use half of the letters:

    enter image description here

    I used the floor function, so I calculate the letter, which appears in an odd amount, correct.

    So how many permutations are in the first half? This is a case of distinct permutation, so we get

    enter image description here

    possibilities.

    For your example: string = "aaabbbb";

    We get: #a=3, #b=4. Therefore

    enter image description here

    We get 3 palindroms, these are "abbabba" , "bbaaabb" and "bababab", like you posted.

    So, if you have a very large string:

    1. Count the amounts of each letter
    2. Check, if there is only 1 letter that appears in an odd amount. It there are more, you can't create palindroms.
    3. Use the formular to calculate the number of different palindroms.