G - Longest Y Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

Y と . からなる文字列 S が与えられます。

次の操作を 0 回以上 K 回以下行うことができます。

  • S の隣り合う 2 文字を入れ替える

操作後に、Y を最大で何個連続させることができますか？

制約

  • 2 \leq |S| \leq 2 \times 10^5
  • S の各文字は Y または . である
  • 0 \leq K \leq 10^{12}
  • K は整数である

入力

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

S
K

出力

答えを出力せよ。

入力例 1

YY...Y.Y.Y.
2

出力例 1

3

S の 6,7 文字目および 9,10 文字目を入れ替えて YY....YYY.. とすると、7 文字目から 9 文字目で Y が 3 個連続しています。
Y を 4 個以上連続させることはできないので、答えは 3 です。

入力例 2

YYYY....YYY
3

出力例 2

4

Score : 600 points

Problem Statement

Given is a string S consisting of Y and ..

You can do the following operation on S between 0 and K times (inclusive).

  • Swap two adjacent characters in S.

What is the maximum possible number of consecutive Ys in S after the operations?

Constraints

  • 2 \leq |S| \leq 2 \times 10^5
  • Each character of S is Y or ..
  • 0 \leq K \leq 10^{12}
  • K is an integer.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the answer.

Sample Input 1

YY...Y.Y.Y.
2

Sample Output 1

3

After swapping the 6-th, 7-th characters, and 9-th, 10-th characters, we have YY....YYY.., which has three consecutive Ys at 7-th through 9-th positions.
We cannot have four or more consecutive Ys, so the answer is 3.

Sample Input 2

YYYY....YYY
3

Sample Output 2

4