删除回文子序列

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
46.67%(35/75)
Description:

给你一个字符串 s,它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文子序列。

返回删除给定字符串中所有字符(字符串为空)的最小删除次数。

「子序列」定义:如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到,那么这个字符串就是原字符串的一个子序列。简单来说,就是按顺序从原字符串中挑一些字符出来组成的字符串,就是子序列。

「回文」定义:如果一个字符串向后和向前读是一致的,那么这个字符串就是一个回文。


Input:

可能有多组数据。
每组数据第一行为n,代表这组数据字符串的长度,1 <= n <= 10^6。
第二行是长度为n的字符串,由字母 'a' 或 'b'组成 

Output:

每组输出一行,仅包含一个正整数。

Sample Input:
2
aa
3
aab
5
baabb
Sample Output:
1
2
2

Submit