P3718 [AHOI2017 Middle School Division] alter

There are $n$ lamps in a row. Some lamps are on, and some are off. Keke wants the lamps to be alternating. He defines the ugliness of a row of lamps as the number of lamps in the longest consecutive segment that are all on or all off. Keke can press switches at most $k$ times. Each operation toggles the state of one lamp: if it was on, it becomes off; otherwise, it becomes on. Given the current states of the lamps, find the minimal ugliness after the operations.

The first line contains two integers $n, k$. The second line is a string of length $n$ consisting of two characters: `N` and `F`. Here, `N` means the lamp is on, and `F` means the lamp is off.

Output the minimal ugliness.

$30\%$ of the testdata: $1\le k \le n\le 20$. $50\%$ of the testdata: $1\le k \le n\le 300$. Another $15\%$ of the testdata: $1\le k \le n\le 10^5$, and the string is all `N` or all `F`. $100\%$ of the testdata: $1\le k \le n\le 10^5$. This problem includes hack testdata. Translated by ChatGPT 5