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 Y
s 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
andY
.
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 Y
s 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 consecutiveY
s at positions 1, 2. - If you choose the 2-nd character, the resulting string is
XXXYX
, with no pair of consecutiveY
s. - If you choose the 3-rd character, the resulting string is
XYYYX
, with two pairs of consecutiveY
s at positions 2, 3 and 3, 4. - If you choose the 4-th character, the resulting string is
XYXXX
, with no pair of consecutiveY
s. - If you choose the 5-th character, the resulting string is
XYXYY
, with one pair of consecutiveY
s 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.