[Tyvj 1966]rainbow与freda染旗

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 shimi.in 输出文件 shimi.out

【题目背景】

Freda：aya Rainbow，怎么没看见你城堡挂旗子呀？
Rainbow：我城堡旗子太难看了肿么办T_T
Freda：lala~那好办，我可以帮你染色呀~
Rainbow：嗯嗯，那就试试吧~ 

【题目描述】

Rainbow城堡的旗子是一个有N个基本单位的长条>_<，每个单位都会被染成前m个大写字母当中的一个颜色。可是，Rainbow认为，两个相邻的单位有相同的颜色很难看的说。所以，Rainbow需要改动一些单位的颜色，使得不存在两个相邻的单位颜色相同。当然了，那些被改动的单位改动之后的颜色也是前m个大写字母当中的一个。Rainbow想请你帮忙计算，它最少要改动多少个单位的颜色才能让旗子好看呢？

【输入格式】

第一行两个整数N、m，表示旗子组成的基本单位数目和颜色的范围。
接下来一行一个长度为N的字符串，字符串的每个字符都是在前m个大写字母的范围内的，表示Rainbow的旗帜。

【输出格式】

 一行一个整数表示Rainbow最少改动的单位数目。

【样例输入】 

6 3
ABBACC

【样例输出】 

2

【提示】


每个测试点1s
样例解释:一种改动方法是ABCACA。当然，还可能有别的改动方法。
对于30%的数据，N<=20.
对于100%的数据，N<=10^5,1<=m<=26.

【来源】

Tyvj 1966