Singularity Cup P2 - Reverse Substring Partitioning

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type

You are given a string S of length N, only consisting of the lowercase letters a-z.

Let us define an RSP (Reverse Substring Partition) as an operation where you partition S into two non-empty contiguous substrings, reverse both substrings, and merge the two letters that touch in the middle of the partitions into one.

In order to perform an RSP, it is required that during the final step, the last letter of the leftmost partition is the same as the first letter of the rightmost partition so they can be merged. Otherwise, this operation cannot be performed. More formally, you may perform an RSP by partitioning S into two non-empty substrings A and B where A + B = S if and only if the last letter of A when reversed is equal to the first letter of B when reversed.

After performing any number of RSPs, what is the minimum possible length of S?


1 \le N \le 10^6

S only contains lowercase letters from the English alphabet.

Input Specification

The first line of input contains an integer N.

The next line of input contains N lowercase letters representing S.

Output Specification

Output a single integer, the smallest possible resulting length of S.

Sample Input


Sample Output



There are no comments at the moment.