#include <bits/stdc++.h>
using namespace std;
string str;
int dp[500007][28];
int n, k;
int solve(int pos, int prev) {
  if (pos > str.size()) {
    return 0;
  }
  if (dp[pos][prev] != -1) {
    return dp[pos][prev];
  }
  int ret = 1 << 29;
  int ch = str[pos] - 65;
  if (ch != prev) {
    ret = min(ret, solve(pos + 1, ch));
  }
  for (int i = 0; i < k; i++) {
    if (i == ch || i == prev) {
      continue;
    }
    ret = min(ret, 1 + solve(pos + 1, i));
  }
  return dp[pos][prev] = ret;
}
void path(int pos, int prev) {
  if (pos == str.size()) {
    return;
  }
  int ch = str[pos] - 65;
  if (ch != prev && dp[pos][prev] == dp[pos + 1][ch]) {
    char c = ch + 65;
    cout << c;
    path(pos + 1, ch);
    return;
  } else {
    for (int i = 0; i < k; i++) {
      if (i == ch || i == prev) {
        continue;
      }
      if (dp[pos + 1][i] + 1 == dp[pos][prev]) {
        char c = i + 'A';
        cout << c;
        path(pos + 1, i);
        return;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  cin >> str;
  memset(dp, -1, sizeof(dp));
  k = min(k, 10);
  int ans = solve(0, 27);
  cout << ans << endl;
  path(0, 27);
  return 0;
}
