Description
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.
Input
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.
Output
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.
Sample Input
6 3
ABBACC
2
ABCACA
3 2
BBB
1
BAB
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int main() 6 { 7 int n,m; 8 char s[500100]; 9 while(scanf("%d%d",&n,&m)!=EOF) 10 { 11 scanf("%s",s); 12 int i,ans=0; 13 m+=64; 14 if(n==1) 15 { 16 cout<<ans<<endl<<s<<endl; 17 continue; 18 } 19 if(m==66) 20 { 21 int l=0,r=0; 22 for(i=0;i<n;i++) 23 if(i%2==0) 24 { 25 if(s[i]=='B') l++; 26 else r++; 27 } 28 else 29 { 30 if(s[i]=='A') l++; 31 else r++; 32 } 33 if(l<r) 34 { 35 cout<<l<<endl; 36 for(i=0;i<n;i++) 37 if(i%2==0) cout<<'A'; 38 else cout<<'B'; 39 } 40 else 41 { 42 cout<<r<<endl; 43 for(i=0;i<n;i++) 44 if(i%2==0) cout<<'B'; 45 else cout<<'A'; 46 } 47 cout<<endl; 48 continue; 49 } 50 s[n]='#'; 51 for(i=1;i<n;i++) 52 if(s[i]==s[i-1]) 53 { 54 ans++; 55 for(int j=65;j<=m;j++) 56 if(j==s[i]||j==s[i+1]) continue; 57 else 58 { 59 s[i]=j; 60 break; 61 } 62 } 63 s[n]=' '; 64 cout<<ans<<endl<<s<<endl; 65 66 } 67 return 0; 68 }