301174: CF219C. Color Stripe
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Color Stripe
题意翻译
给出一个字符串,只包含k种字符,问最少修改多少个字符(不增长新的种类)能够得到一个新的字符串,这个字符串满足相邻的字符没有相同的。题目描述
A colored stripe is represented by a horizontal row of $ n $ square cells, each cell is pained one of $ k $ colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to $ k $ to repaint the cells.输入输出格式
输入格式
The first input line contains two integers $ n $ and $ k $ ( $ 1<=n<=5·10^{5}; 2<=k<=26 $ ). The second line contains $ n $ uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first $ k $ English letters may be used. Each letter represents the color of the corresponding cell of the stripe.
输出格式
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.
输入输出样例
输入样例 #1
6 3
ABBACC
输出样例 #1
2
ABCACA
输入样例 #2
3 2
BBB
输出样例 #2
1
BAB