#Z6029. 回文编辑

回文编辑

题目描述

给定一个长度不超过 n 的字符串 s,如果 s 中的一个子序列是回文,那么我们就可以从 s 中移除这个子序列,求最少经过多少步我们可以移除整个字符串 s。如:我们可以从"dqewfretd"中移除 "defed",剩下的字符串即:"qwrt"。

输入格式

第1行包含1个整数 n(1n18)n (1\le n \le18)

第2行包含n个字符的字符串 ss

输出格式

输出一个整数,表示最小步数。

样例输入 #1

9
dqewfretd

样例输出 #1

5

样例输入 #2

6
abctab

样例输出 #2

2