특별한 부분 문자열

문자열의 부분 문자열이란 문자열에서 연속한 문자들을 이어 붙인 것이다. 예를 들어 BC는 ABCD의 두 번째 문자에서 시작하는 부분 문자열이고, ABC는 ABCD의 첫 번째 문자에서 시작하는 부분 문자열이다. ABCD 자기 자신도 ABCD의 부분 문자열이다.

이 문제에서는 같은 문자로만 이루어진 비어 있지 않은 부분 문자열을 특별한 부분 문자열이라고 부른다. 예를 들어 B와 CC는 ABBCCC의 특별한 부분 문자열이지만, ABBC와 BC는 특별한 부분 문자열이 아니다.

길이 N인 문자열 S와 정수 K가 주어진다. S에 길이 K인 특별한 부분 문자열이 존재하도록 만들기 위해 바꿔야 하는 문자의 최소 개수를 구하시오.

예를 들어 N = 6, K = 4, S = ABBCCC라 하자. 이때 S의 세 번째 문자를 C로 바꾸면(ABBCCC → ABCCCC) 길이 4인 특별한 부분 문자열 CCCC가 생기므로, 바꿔야 하는 문자는 1개이다.

첫 줄에 두 정수 N K (1 ≤ K ≤ N ≤ 100 000)가 주어진다. N은 문자열의 길이, K는 만들어야 하는 특별한 부분 문자열의 길이이다. 다음 줄에 N개의 대문자로 이루어진 문자열 S가 주어진다. 즉, Si ∈ [A-Z]이다.

주어진 S에 길이 K인 특별한 부분 문자열이 존재하도록 만들기 위해 바꿔야 하는 문자의 최소 개수를 한 줄에 출력한다.