219C.md (1106B)
1 Source: https://codeforces.com/problemset/problem/219/C 2 3 C. Color Stripe 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 Input 24 25 The first input line contains two integers *n* and *k* (1 ≤ *n* ≤ 5·105; 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. 26 27 Output 28 29 Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe. 30 31 Examples 32 33 Input 34 35 ``` 36 6 3 37 ABBACC 38 ``` 39 40 Output 41 42 ``` 43 2 44 ABCACA 45 ``` 46 47 Input 48 49 ``` 50 3 2 51 BBB 52 ``` 53 54 Output 55 56 ``` 57 1 58 BAB 59 ```