## An Animal Contest 2 P1 - Koala Konundrum

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

The 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 .

6
dababy

2

#### Explanation 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
whentheimposterissus

#### Sample Output 2

8

• commented on Nov. 23, 2023, 5:06 a.m.

I love how a simple observation drastically simplifies the time complexity from way too big for 2 seconds to linear!

• commented on Aug. 27, 2023, 3:54 a.m.

Why can't you split dababy into dab and aby, giving no palindromes?

• commented on Aug. 27, 2023, 9:12 a.m.

All of the strings you split into need to be palindromes. Splitting into dab and aby is invalid since neither are palindromes.

• commented on Aug. 29, 2023, 6:48 a.m.

Thanks, solved!

• commented on Oct. 7, 2021, 1:02 a.m.

I don't even want to imagine a koala muttering "whentheimposterissus". Would defenitely be... interesting

• commented on May 17, 2021, 12:43 a.m.

this problem is sus