회문

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 N의 대문자 문자열을 최소 횟수로 글자를 바꿔 팰린드롬으로 만들고, 사전순으로 가장 앞선 결과를 출력합니다.

문제

케빈은 정보올림피아드 예선에서 회문 문제로 만점을 받았다. 이를 본 선생님은 길이가 다양한 회문을 다루는 조금 더 어려운 문제를 그에게 냈다.

숫자 배열의 경우와 마찬가지로, 앞에서 읽으나 뒤에서 읽으나 같은 텍스트를 회문이라고 한다. 예를 들어 ABBA는 뒤에서부터 읽어도 ABBA이므로 회문이다. 반면 ABCD는 뒤에서부터 읽으면 DCBA가 되므로 회문이 아니다.

주어진 텍스트를 회문으로 바꾸는 데 필요한 글자 교체 횟수가 가장 적은 방법을 찾는 프로그램을 작성하라.

첫 줄에 정수 $N$ ( $1 \le N \le 300$ )이 주어진다.

둘째 줄에는 $N$ 개의 대문자 라틴 알파벳(A ... Z)으로 이루어진 텍스트가 주어진다.

첫 줄에 주어진 텍스트를 회문으로 바꾸는 데 필요한 글자 교체 횟수의 최솟값 $K$ 를 출력한다.

둘째 줄에는 만들어진 회문을 출력한다. 최소 교체 횟수로 만들 수 있는 회문이 여러 개라면 알파벳 순서로 가장 앞선 것을 출력한다.