102293: [AtCoder]ABC229 D - Longest X

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给定一个以 `X` 和 `.` 组成的的字符串 $S$。 你可以对 $S$ 进行 $0 \sim K$ 次以下操作(包含 $0$ 和 $K$ 次)。 * 把 $S$ 中的一个 `.` 替换成 `X`。 求操作之后,$S$ 中连续 `X` 的最大数量为多少?

Output

分数:400分

问题描述

给定一个由X.组成的字符串$S$。

你可以对$S$进行0到$K$次(包括0次和$K$次)以下操作:

  • 将一个.替换为X

操作后,$S$中连续的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

将第7个和第9个位置的X替换为X后,我们得到XX...XXXXX.,其中在第6个到第10个位置有5个连续的X
我们不能有6个或更多的连续X,所以答案是5。


样例输入2

XXXX
200000

样例输出2

4

允许进行0次操作。

加入题单

上一题 下一题 算法标签: