#117. 土拨鼠月老的计划
土拨鼠月老的计划
Background
众所周知, 情人节11月11日就要到了, 土拨鼠月老乐乐开始了忙碌的工作, 她最喜欢的事情就是组织相亲活动了.
Description
一排土拨鼠会挑选一个最喜欢的小写字母贴在自己的身上, 只有挑选到相同字母的鼠鼠, 才可以配对, 无所谓男鼠女鼠. 月老的作用就是让两个相邻的鼠鼠挨在一起, 这样他们就成双成对了, 那么月老乐乐必须选择一些鼠鼠离开舞台. (注意, 乐乐不可以更改鼠鼠们的位置), 比如这样的鼠鼠们, 只需要让离开, 那么就会达到相邻的状态.
乐乐可以让任意鼠鼠离开舞台, 他希望最终舞台上的鼠鼠们全都成双成对, 注意三人行是不被允许的.
有爱心的乐乐希望你帮帮她计算一下她最少需要让多少鼠鼠离开舞台.(注意: 0只鼠鼠在舞台上, 也是可行的状态)
Format
Input
第1行一个整数n, 表示有n只鼠鼠
第2行一个字符串, 表示这一排鼠鼠们身上的小写字母
Output
输出一个整数, 表示让多少鼠鼠下台, 即可让舞台上的鼠鼠们成双成对.
Samples
6
abbxxc
2
样例解释1
可以发现, 让下台后, 字符串变为, 满足乐乐的要求
4
abab
2
样例解释2
可以发现, 要求所有的或者所有的下台, 可以满足乐乐的要求
4
abcd
4
样例解释3
可以发现, 没有鼠鼠能找到对象, 需要让所有鼠鼠下台, 才可以满足乐乐的要求
Limitation
对于 的数据,有 。
Statistics
Related
In following contests: