An Animal Contest 2 P1 - Koala Konundrum
View as PDFThe koalas are having fun together at the annual Easter festival. Unfortunately, their festival is interrupted by the muttering of a strange koala witch. The koalas don't understand at first, but they eventually notice a pattern. The witch mutters letters, forming a string
, then a number
. The koalas don't understand the meaning of
, so they rearrange the letters of
to look for a clue. To start off, for each permutation of
, they give it a score
, with
representing the minimal number of palindromic substrings this permutation can be split into. Note that each character in the permutation must belong to exactly one substring. After doing some calculations, the koalas notice that
is just the minimum score of
across all permutations of
!
Now that the koalas know the rule, they devise a game. They will listen to the witch's string and predict before she says it herself. However, the koalas don't have the brain power to calculate this number and need you to find the answer for them!
A palindrome is a string that is the same as its reverse. For example, strings tacocat, noon, x, and bbbb are palindromes, while strings abab and osuhow are not.
Constraints
All characters in string are lowercase English letters.
Input Specification
The first line contains the integer , the number of characters in string
.
The second line contains the string .
Output Specification
Output an integer , the minimum score of
across all permutations of
.
Sample Input 1
6
dababySample Output 1
2Explanation for Sample 1
We arrange the above string into bybada and split it into byb and ada, giving us palindromic substrings. It can be proven that this number is minimal.
Sample Input 2
20
whentheimposterissusSample Output 2
8
Comments
AMOGUS
whentheimposterissus
I love how a simple observation drastically simplifies the time complexity from way too big for 2 seconds to linear!
Why can't you split
dababyintodabandaby, giving no palindromes?All of the strings you split into need to be palindromes. Splitting into
dabandabyis invalid since neither are palindromes.Thanks, solved!
I don't even want to imagine a koala muttering "whentheimposterissus". Would defenitely be... interesting
this problem is sus