30400번 - 팰린드롬 제거

문제

이안이는 팰린드롬을 싫어한다. 팰린드롬인 단어를 보면 당장 그 단어를 지워야 할 정도로 팰린드롬을 매우 싫어한다. 팰린드롬은 'level', 'bob'과 같이 양쪽으로 읽었을 때 동일하게 읽히는 단어이다.

이제 이안이는 팰린드롬이 아닌 단어더라도 부분문자열 중 팰린드롬이 있기만 해도 그 단어를 지우고 싶을 정도가 되었다. 하지만 그렇게 하면 남는 단어가 거의 없을 것이다. 대신 글자 몇 개를 부숴 길이가 $M$ 이상인 팰린드롬인 부분문자열이 없도록 만들려고 한다.

글자를 부수면 부서진 글자가 포함된 문자열은 팰린드롬이 될 수 없다. 예를 들어 abcba에서 가운데 c를 부수면 ab#ba가 되고, 이는 팰린드롬이 아니다.

banana는 부분문자열 중 anana, ana, nan이 팰린드롬이므로 글자를 부숴야 한다. $M = 2$인 경우 두 번째 a를 부수면 ban#na와 같이 길이가 2ドル$ 이상인 팰린드롬인 부분문자열이 없도록 할 수 있다.

글자를 부수는 건 매우 귀찮은 일이다. 이안이를 도와 부숴야 하는 글자 개수의 최솟값을 구해보자.

입력

첫 번째 줄에 단어의 길이 $N,ドル 싫어하는 팰린드롬의 길이인 $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 길이 $N$인 단어가 한 줄에 주어진다.

출력

길이가 $M$ 이상인 팰린드롬인 부분문자열이 없도록 만들기 위해 부숴야 하는 글자 개수의 최솟값을 출력한다.

제한

• 2ドル\le N\le 2 \times 10^5$
• 2ドル\le M \le N$
• 주어진 문자열은 알파벳 소문자로만 이루어져 있다.

노트