#include <bits/stdc++.h>
using namespace std;
int dp[500005][28];
int ar[500005];
int p[500005][28];
int ans[500005];
string st;
int main() {
  int a, b, c, d, e, x, y, z, k, n;
  cin >> n >> k;
  cin >> st;
  for (a = 0; a < n; a++) ar[a + 1] = st[a] - 'A';
  for (a = 1; a <= n; a++) {
    for (b = 0; b < k; b++) {
      dp[a][b] = 500005;
    }
  }
  for (a = 1; a <= n; a++) {
    for (b = 0; b < k; b++) {
      if (ar[a] == b)
        c = 0;
      else
        c = 1;
      for (d = 0; d < k; d++) {
        if (b == d) continue;
        if (dp[a][b] > dp[a - 1][d] + c) {
          dp[a][b] = min(dp[a][b], dp[a - 1][d] + c);
          p[a][b] = d;
        }
      }
    }
  }
  x = 500005;
  for (a = 0; a < k; a++)
    if (x > dp[n][a]) {
      x = dp[n][a];
      b = a;
    }
  cout << x << endl;
  a = n;
  while (a >= 1) {
    ans[a] = b;
    b = p[a][b];
    a--;
  }
  for (a = 1; a <= n; a++) printf("%c", ans[a] + 'A');
  printf("\n");
  return 0;
}
