El problema consiste en determinar el número mínimo de cambios de color necesarios para asegurar que ninguna celda adyacente en una fila de n celdas tenga el mismo color. Se dispone de k colores para realizar estos cambios.

Entrada

La entrada consta de dos enteros en la primera línea: n (la cantidad de celdas, 1 ≤ n ≤ 5·105) y k (la cantidad de colores disponibles, 2 ≤ k ≤ 26). La segunda línea contiene una cadena de n letras mayúsculas del alfabeto inglés, representando los colores iniciales de las celdas. La letra 'A' corresponde al primer color, 'B' al segundo, y así sucesivamente, hasta la k-ésima letra del alfabeto.

Salida

Se debe imprimir un solo entero: la cantidad mínima de repintados requeridos. En la segunda línea, se imprimirá una posible configuración de la fila de celdas después de los repintados.

Ejemplo 1

Entrada

6 3
ABBACC

Salida

2
ABCACA

Ejemplo 2

Entrada

3 2
BBB

Salida

1
BAB

Consideraciones Especiales para k=2

Cuando solo hay dos colores disponibles (k=2), la única condición es que las celdas adyacentes deban tener colores alternos. Existen dos patrones posibles que satisfacen esta condición: el patrón ABABA... y el patrón BABAB.... Para minimizar los cambios, debemos evaluar cuántas celdas difieren de cada uno de estos dos patrones y elegir el que requiera menos modificaciones.

Por ejemplo, si la secuencia inicial es BBB y k=2, podemos elegir entre:

• Patrón 1: BAB. Cambios necesarios: 1 (la segunda B a A).
• Patrón 2: ABA. Cambios necesarios: 2 (todas las B a A).

Seleccionamos el patrón BAB, que requiere 1 cambio.

Algoritmo General (k > 2)

Para k > 2, el problema se vuelve más complejo y puede ser abordado de manera más general. Se puede observar que cuando existen dos celdas consecutivas con el mismo color, al menos una de ellas debe ser repintada. La estrategia consiste en identificar segmentos de celdas idénticas y decidir cómo modificarlos para cumplir la restricción. Si encontramos un segmento de celdas iguales, por ejemplo, ...XY Z Z Z Z W..., donde Z es el color repetido, podemos pensar en cómo reemplazar las celdas Z. Una heurística podría ser identificar el color que se usa con menos frecuencia en los alrededores (X y W) y usarlo para reemplazar la secuencia Z de manera alternante, siempre que no sea igual a sus vecinos inmediatos. La clave está en minimizar el número total de cambios.

El código proporcionado implementa una lógica específica para manejar el caso k=2 de forma separada y luego un enfoque heurístico para k > 2, que parece intentar agrupar celdas consecutivas idénticas y repararlas eligiendo un color distinto al de los bordes del segmento y al de los colores ya utilizados en la reparación dentro del segmento.

El código original para k > 2 parece estar diseñado para identificar bloques de celdas adyacentes con el mismo color. Dentro de un bloque, se busca un color alternativo que no sea ni el color anterior ni el siguiente al bloque, ni los colores ya usados en la reparación del bloque. Si el color anterior y el siguiente al bloque son iguales, se elige un color completamente nuevo. El objetivo es llenar el bloque de forma alternante con este nuevo color elegido.

El número total de repintados se calcula contando la mitad de la longitud de cada bloque de celdas idénticas (ya que cada dos celdas idénticas en un bloque de tamaño par implican un cambio, y lo mismo para un bloque de tamaño impar, pero la lógica se simplifica a la mitad de la longitud del bloque en este enfoque).