## Editorial for An Animal Contest 2 P1 - Koala Konundrum

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Let us define an odd letter as a letter with an odd number of occurrences and an even letter as a letter with an even number of occurrences. We record the number of times that each letter appears in , and determine the number of odd and even letters.

A key observation is that we can combine all even letters into a single palindrome. For example, if the letters `a`

and `b`

occur twice, they can form a single palindrome of the form `abba`

. Thus, is simply , as we have a minimum of one palindrome.

**Time Complexity:**

## Comments

You might be wondering, why is it max(1, odd_letter_count) and not max(1, odd_letter_count+1) since there is one chunk of palindrome for even numbers? But I noticed that I can incorporate one odd letter into the even letter palindromic substring. For example, from the "dababy" example, I can create "abba" just from even occurrences but I could also make "abdba" or "abyba" by mixing a odd letter in there. The remaining odd letters can only be palindromic when they are grouped by the same letter. Therefore the answer is max(1, odd_letter_count). Hopefully my interpretation was correct.

orz suguru