题目描述

给定一个长度为 $n$ 的字符串 $s$，$s$ 仅由单词表中前 $k$ 个单词对应的大写英文字母组成。

举些例子：

• 当 $k = 3$ 时，$s$ 仅能由字符 $\mathtt{A}$、$\mathtt{B}$、$\mathtt{C}$ 组成；
• 当 $k = 6$ 时，$s$ 仅能由字符 $\mathtt{A}$、$\mathtt{B}$、$\mathtt{C}$、$\mathtt{D}$、$\mathtt{E}$、$\mathtt{F}$ 组成

你可以替换字符串中的任意一个字符，但是也仅允许使用单词表中前 $k$ 个单词对应的大写英文字母进行替换。

你希望替换掉最少的字符，使得字符串中任意两个相邻的字符不相同。

求：最少需要替换掉几个字符？

输入格式

第一行，两个整数 $n$ 和 $k$（$1 \le n \le 5 \cdot 10^5; 2 \le k \le 26$）

第二行，一个长度为 $n$ 的字符串 $s$。$s$ 仅由单词表中前 $k$ 个单词对应的大写英文字母组成。

输出格式

输出一个整数，表示要使字符串 $s$ 中任意两个相邻的字符都不相同所需替换掉的最少单词个数。

6 3
ABBACC

2

3 2
BBB

1

说明/提示

样例解释

样例1：一种最优方案是将 $s_3$ 替换为 $\mathtt{C}$，将 $s_5$ 替换为 $\mathtt{B}$，则 $\mathtt{ABBACC} \rightarrow \mathtt{ABCABC}$

样例2：一种最优方案是将 $s_2$ 替换为 $\mathtt{B}$，则 $\mathtt{BBB} \rightarrow \mathtt{BAB}$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10; k \le 3$
• 对于 $60\%$ 的数据，$n \le 1000; k \le 10$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5; 2 \le k \le 26$，且字符串 $s$ 仅由单词表中前 $k$ 个单词对应的大写英文字母组成