CF219C Color Stripe

一条彩色条纹由 $n$ 个水平排列的方格组成，每个方格被涂成 $k$ 种颜色中的一种。你的任务是重新涂色最少数量的方格，使得任何两个相邻方格的颜色都不相同。你可以使用 $1$ 到 $k$ 中的任意颜色重新涂色方格。

第一行输入两个整数 $n$ 和 $k$（$1 \leq n \leq 5 \cdot 10^{5}$，$2 \leq k \leq 26$）。 第二行输入 $n$ 个大写英文字母。"A" 表示第一种颜色，"B" 表示第二种颜色，以此类推。将会只用前 $k$ 个大写英文字母。每个字母表示对应方格的颜色。

输出一行一个整数，表示所需重新涂色的最小数目。 第二行输出任意一种可能的重新涂色后的条纹。

由 ChatGPT 5 翻译