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: WilliamWu277

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 S, 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, X is simply \max(1, \text{odd_letter_count}), as we have a minimum of one palindrome.

Time Complexity: \mathcal{O}(N)

Comments


  • 14
    suguruchhaya  commented on May 13, 2021, 8:59 p.m.

    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.