题目描述

给定一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成。你可以对该字符串进行如下操作：每次操作可以删除一个连续的子串，前提是该子串中的所有字母都相同。例如，从字符串 abbbbaccdd 删除子串 bbbb 后，得到字符串 aaccdd。

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

输入格式

第一行包含一个整数 $n$（$1 \le n \le 500$），表示字符串 $s$ 的长度。

第二行包含字符串 $s$（$|s| = n$），该字符串仅由小写拉丁字母组成。

输出格式

输出一个整数，表示删除字符串 $s$ 所需的最少操作次数。

说明/提示

由 ChatGPT 4.1 翻译

样例

5
abaca

3

8
abcddcba

4