An Animal Contest 2 P1 - Koala Konundrum - DMOJ: Modern Online Judge

An Animal Contest 2 P1 - Koala Konundrum

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 $N$ $N$ letters, forming a string $S$ $S$ , then a number $X$ $X$ . The koalas don't understand the meaning of $X$ $X$ , so they rearrange the letters of $S$ $S$ to look for a clue. To start off, for each permutation of $S$ $S$ , they give it a score $Y$ $Y$ , with $Y$ $Y$ 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 $X$ $X$ is just the minimum score of $Y$ $Y$ across all permutations of $S$ $S$ !

Now that the koalas know the rule, they devise a game. They will listen to the witch's string and predict $X$ $X$ 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

$1 \leq N \leq 10^6$ $1 \leq N \leq 10^{6}$

All characters in string $S$ $S$ are lowercase English letters.

Input Specification

The first line contains the integer $N$ $N$ , the number of characters in string $S$ $S$ .

The second line contains the string $S$ $S$ .

Output Specification

Output an integer $X$ $X$ , the minimum score of $Y$ $Y$ across all permutations of $S$ $S$ .

Sample Input 1

Copy

6
dababy

Sample Output 1

Copy

Explanation for Sample 1

We arrange the above string into bybada and split it into byb and ada, giving us $2$ $2$ palindromic substrings. It can be proven that this number is minimal.

Sample Input 2

Copy

20
whentheimposterissus

Sample Output 2

Copy

Comments

-1

phankhoinguyenha commented on Sept. 20, 2024, 4:36 a.m.

AMOGUS

-2

EthFng64 commented on Sept. 13, 2024, 12:38 a.m.

whentheimposterissus

-2

epicgamergirl999 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!

-2

Viv_CCGS commented on Aug. 27, 2023, 3:54 a.m. ← edited →

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

1

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

-2

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

Thanks, solved!

20

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

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

6

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

this problem is sus