← 返回题目列表

Codeforces · 1132/F

F. 清除字符串

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字母组成。您可以对该字符串应用一些操作:如果您删除的子字符串中的所有字母都相等,则在一次操作中您可以删除该字符串的某些连续子字符串。例如,从字符串 abbbbaccdd 中删除子字符串 bbbb 后,我们得到字符串 aaccdd。

计算删除整个字符串$$$s$$$的最少操作次数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 字符串 $$$s$$$ 的长度。

第二行包含由小写拉丁字母组成的字符串 $$$s$$$ ($$$|s| = n$$$)。

输出

输出单个整数 — 删除字符串 $$$s$$$ 的最少操作次数。

示例

输入 #1

5
abaca

输出 #1

3

输入 #2

8
abcddcba

输出 #2

4