Special Substring

Interview

Time limit1sMemory limit512 MB

Summary

Given a string and K, find the fewest character changes needed so some window of K consecutive characters becomes a single repeated letter.

Level: Medium5 of 10
Topics: Sliding window, String, Brute force, Array
Solved: No attempts yet

Problem

A substring of a string is a contiguous sequence of characters from the string. For example, BC is a substring of ABCD that starts at the second character of ABCD. Another example: ABC is a substring of ABCD that starts at the first character of ABCD. Note that ABCD itself is also a substring of ABCD.

In this problem, a special substring is a non-empty substring that contains only one kind of character. For example, B and CC are special substrings of ABBCCC, while ABBC and BC are not special substrings.

You are given a string S of length N and an integer K. Find the minimum number of characters of S that must be changed so that S contains a special substring of length K.

For example, let N = 6, K = 4, and S = ABBCCC. Changing the third character of S to C (ABBCCC to ABCCCC) produces the special substring CCCC of length 4, so one character has to be changed.

Input

The first line contains two integers N K (1 ≤ K ≤ N ≤ 100 000): the length of the string and the length of the special substring that should be produced. The next line contains a string S of N uppercase letters, that is, Si ∈ [A-Z].

Output

Output one line with an integer: the minimum number of characters of S that must be changed so that the given S contains a special substring of length K.

Examples4

Example 1
Input
```
6 4
ABBCCC
```
Expected output
```
1
```
Example 2
Input
```
9 6
AABCABBBA
```
Expected output
```
2
```
Example 3
Input
```
10 7
BAABAABAAB
```
Expected output
```
2
```
Example 4
Input
```
6 2
INNCCC
```
Expected output
```
0
```