D - Longest X

Contest Duration: 2021-11-27(Sat) 12:00 - 2021-11-27(Sat) 13:40 (local time) (100 minutes) Back to Home

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

XX...X.X.X.
2

出力例 1Copy

Copy

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

入力例 2Copy

Copy

XXXX
200000

出力例 2Copy

Copy

操作を行う回数は $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 1Copy

Copy

XX...X.X.X.
2

Sample Output 1Copy

Copy

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 2Copy

Copy

XXXX
200000

Sample Output 2Copy

Copy

It is allowed to do zero operations.