配点 : $500$ 点

問題文

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

制約

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

入力

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

$N$ $K$

$S$

出力

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

5 1
XYXYX

2

選ぶのは $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$ です．

5 4
XYXYX

2

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