B - XYYYX Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 同士が隣り合う箇所の個数の最大値を出力せよ．

入力例 1

5 1
XYXYX

出力例 1

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 です．

入力例 2

5 4
XYXYX

出力例 2

2

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

Score : 500 points

Problem Statement

You are given a string S of length N consisting of X and Y. You will choose K characters at distinct positions in S and change each of them: X becomes Y and Y becomes X. Find the maximum possible number of pairs of consecutive Ys in the resulting string.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N
  • S is a string of length N consisting of X and Y.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of pairs of consecutive Ys in the resulting string.

Sample Input 1

5 1
XYXYX

Sample Output 1

2

You will choose one character.

  • If you choose the 1-st character, the resulting string is YYXYX, with one pair of consecutive Ys at positions 1, 2.
  • If you choose the 2-nd character, the resulting string is XXXYX, with no pair of consecutive Ys.
  • If you choose the 3-rd character, the resulting string is XYYYX, with two pairs of consecutive Ys at positions 2, 3 and 3, 4.
  • If you choose the 4-th character, the resulting string is XYXXX, with no pair of consecutive Ys.
  • If you choose the 5-th character, the resulting string is XYXYY, with one pair of consecutive Ys at positions 4, 5.

Thus, the sought maximum number is 2.

Sample Input 2

5 4
XYXYX

Sample Output 2

2

It is optimal to choose the 1-st, 2-nd, 3-rd, and 5-th characters to get YXYYY, or choose the 1-st, 3-rd, 4-th, and 5-th characters to get YYYXY. Note that you may not choose a character at the same position multiple times.