#include <bits/stdc++.h>
using namespace std;
const int N = 5e5, inf = 1e9, NIL = -1;
int n, k;
string s;
vector<char> ans;
int memo[N][30];
int dp(int i = 0, int j = 0) {
  if (i == n) return 0;
  int &ret = memo[i][j];
  if (~ret) return ret;
  ret = inf;
  if (i and s[i] - 'A' + 1 != j)
    ret = dp(i + 1, s[i] - 'A' + 1);
  else
    for (int c = 1; c <= k; ++c)
      if (c != j) ret = min(ret, dp(i + 1, c) + (c != s[i] - 'A' + 1));
  return ret;
}
void build(int i = 0, int j = 0) {
  if (i == n) return;
  int &ret = memo[i][j];
  if (i and s[i] - 'A' + 1 != j and ret == dp(i + 1, s[i] - 'A' + 1)) {
    ans.emplace_back(s[i]);
    build(i + 1, s[i] - 'A' + 1);
  } else {
    for (int c = 1; c <= k; ++c)
      if (c != j and dp(i + 1, c) + (c != s[i] - 'A' + 1) == ret) {
        ans.emplace_back(char(c + 'A' - 1));
        build(i + 1, c);
        return;
      }
  }
}
int main() {
  ios_base::sync_with_stdio();
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> s;
  memset(memo, NIL, sizeof memo);
  cout << dp() << endl;
  build();
  for (char c : ans) cout << c;
  return 0;
}
