← 返回题目列表

Codeforces · 219/C

C. 彩色条纹

中文机器翻译题面 查看原题

彩色条纹由水平行的 n 个方形单元表示,每个单元都涂有 k 种颜色之一。您的任务是重新绘制最少数量的单元格,以便没有两个相邻单元格具有相同的颜色。您可以使用 1 到 k 之间的任何颜色来重新绘制单元格。

输入

第一个输入行包含两个整数 n 和 k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26)。第二行包含n个大写英文字母。字母“A”代表第一种颜色,字母“B”代表第二种颜色,依此类推。可以使用前k个英文字母。每个字母代表条纹相应单元格的颜色。

输出

打印一个整数——所需的最小重画次数。在第二行中打印重新绘制的条纹的任何可能的变体。

示例

输入 #1

6 3
ABBACC

输出 #1

2
ABCACA

输入 #2

3 2
BBB

输出 #2

1
BAB