Lacquer Chopsticks (Chopsticks)

Interview

Time limit1sMemory limit1024 MB

Summary

Given a target color string of length N, find the minimum number of range-paint operations (each painting a contiguous interval one color) needed to produce it.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, String, Greedy
Solved: No attempts yet

Problem

The Japan Ohashi Institute has decided to prepare chopsticks designed to promote chopsticks internationally. The painted part of a chopstick spans N mm from one end, with a color fixed for every 1 mm, and no part is left unpainted. The lacquer used to paint the chopsticks comes in 52 colors.

You, a lacquer artisan, have been asked to paint the chopsticks in the specified colors. Lacquering takes effort, so you want to finish the chopsticks in as few operations as possible.

One operation to paint a chopstick is to choose a contiguous interval and paint that entire interval a single color. Any place already painted also takes the new color. Write a program to find the minimum number of operations needed to finish the chopsticks.

Input

The first line of input contains a single integer N (1 ≤ N ≤ 300). This means the painted part of the chopstick is N mm long.

The second line contains a string of N English letters (A to Z, a to z). The i-th character of the string represents the color from (i − 1) mm to i mm from the end.

Output

Output to standard output. Print a single integer representing the minimum number of operations.

Examples2

Example 1
Input
```
6
JOIIOI
```
Expected output
```
4
```
Example 2
Input
```
15
PlovdivBulgaria
```
Expected output
```
12
```