题目描述

X, Y からなる長さ $N$ の文字列 $S$ が与えられます． $S$ 中の相異なる位置にある $K$ 文字を選び，選んだ文字が X であれば Y に，Y であれば X にそれぞれ置き換えます． 置き換えた後の文字列中で Y 同士が隣り合う箇所は最大でいくつになるかを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $S$

输出格式

置き換えた後の文字列中で Y 同士が隣り合う箇所の個数の最大値を出力せよ．

题目大意

给定一个长为 $n$ 只包含 $X,Y$ 的字符串 $S$，求恰好翻转互不相同的 $K$ 位后，$\sum\limits_{i=1}^{n-1}[S_i=Y][S_{i+1}=Y]$ 的最大值。

5 1
XYXYX

2

5 4
XYXYX

2

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ K\ \leq\ N$
• $S$ は X, Y からなる長さ $N$ の文字列である．

Sample Explanation 1

選ぶのは $1$ 文字だけです． - $1$ 文字目を選ぶと，置き換えた後の文字列は YYXYX となり，$1,\ 2$ 文字目の $1$ 箇所で Y 同士が隣り合っています． - $2$ 文字目を選ぶと，置き換えた後の文字列は XXXYX となり，Y 同士が隣り合っている箇所はありません． - $3$ 文字目を選ぶと，置き換えた後の文字列は XYYYX となり，$2,\ 3$ 文字目と $3,\ 4$ 文字目の $2$ 箇所で Y 同士が隣り合っています． - $4$ 文字目を選ぶと，置き換えた後の文字列は XYXXX となり，Y 同士が隣り合っている箇所はありません． - $5$ 文字目を選ぶと，置き換えた後の文字列は XYXYY となり，$4,\ 5$ 文字目の $1$ 箇所で Y 同士が隣り合っています． 以上より，求める最大値は $2$ です．

Sample Explanation 2

$1,\ 2,\ 3,\ 5$ 文字目を選んで YXYYY とするか，$1,\ 3,\ 4,\ 5$ 文字目を選んで YYYXY とするのが最適です． 同じ位置にある文字を複数回選ぶことはできないことに注意してください．