D - Longest X Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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

S に対して、次の操作を 0 回以上 K 回以下行うことができます。

  • . を X に置き換える

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

制約

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

入力

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

S
K

出力

答えを出力せよ。

入力例 1

XX...X.X.X.
2

出力例 1

5

S の 7 文字目と 9 文字目の . を X に置き換えて XX...XXXXX. とすると、6 文字目から 10 文字目で X が 5 個連続しています。
X を 6 個以上連続させることはできないので、答えは 5 です。

入力例 2

XXXX
200000

出力例 2

4

操作を行う回数は 0 回でも構いません。

Score : 400 points

Problem Statement

Given is a string S consisting of X and ..

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

  • Replace a . with an X.

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

Constraints

  • 1 \leq |S| \leq 2 \times 10^5
  • Each character of S is X or ..
  • 0 \leq K \leq 2 \times 10^5
  • K is an integer.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the answer.

Sample Input 1

XX...X.X.X.
2

Sample Output 1

5

After replacing the Xs at the 7-th and 9-th positions with X, we have XX...XXXXX., which has five consecutive Xs at 6-th through 10-th positions.
We cannot have six or more consecutive Xs, so the answer is 5.

Sample Input 2

XXXX
200000

Sample Output 2

4

It is allowed to do zero operations.