#include <bits/stdc++.h>
using namespace std;
char str[1001000];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    cin >> str[i];
  }
  if (k == 2) {
    int sum = 0, sum1 = 0;
    char tmp = 'A';
    for (int i = 1; i <= n; i++) {
      if (str[i] != tmp) {
        tmp = str[i];
      } else {
        if (tmp == 'A')
          tmp = 'B';
        else
          tmp = 'A';
        sum++;
      }
    }
    tmp = 'B';
    for (int i = 1; i <= n; i++) {
      if (str[i] != tmp) {
        tmp = str[i];
      } else {
        if (tmp == 'A')
          tmp = 'B';
        else
          tmp = 'A';
        sum1++;
      }
    }
    if (sum < sum1) {
      printf("%d\n", sum);
      for (int i = 1; i <= n; i++) {
        if (i % 2 == 0)
          printf("A");
        else
          printf("B");
      }
    } else {
      printf("%d\n", sum1);
      for (int i = 1; i <= n; i++) {
        if (i % 2 == 0)
          printf("B");
        else
          printf("A");
      }
    }
  } else {
    int sum = 0, cnt = 1;
    char tmp = '#';
    char tc;
    for (int j = 0; j < k; j++) {
      if ((j + 'A') != str[n]) {
        tc = j + 'A';
        break;
      }
    }
    str[n + 1] = tc;
    for (int i = 1; i <= n + 1; i++) {
      if (str[i] != tmp) {
        if (cnt == 1) {
          tmp = str[i];
          continue;
        }
        char tc;
        for (int j = 0; j < k; j++) {
          if ((j + 'A') != tmp && (j + 'A') != str[i]) {
            tc = j + 'A';
          }
        }
        if (cnt % 2 == 0) {
          str[i - 1] = tc;
          for (int j = i - 3; (i - j) <= cnt; j -= 2) str[j] = tc;
          sum += 1 + (cnt - 1) / 2;
        } else {
          for (int j = i - 2; (i - j) <= cnt; j -= 2) str[j] = tc;
          sum += cnt / 2;
        }
        cnt = 1;
        tmp = str[i];
      } else {
        cnt++;
      }
    }
    printf("%d\n", sum);
    for (int i = 1; i <= n; i++) printf("%c", str[i]);
  }
  return 0;
}
