102296: [AtCoder]ABC229 G - Longest Y
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
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 Y
s 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 Y
s at $7$-th through $9$-th positions.
We cannot have four or more consecutive Y
s, so the answer is $3$.
Sample Input 2
YYYY....YYY 3
Sample Output 2
4
Input
题意翻译
给你一个字符串 $S$,由 `Y` 和 `.` 构成。 现在你可以最多进行 $k$ 次操作,每次可以交换两个相邻的字符。 请你求出最多 $k$ 次操作后,最长连续字符 `Y` 的长度。Output
分数:$600$分
问题描述
给定一个由Y
和.
组成的字符串$S$。
你可以在$S$上执行$0$到$K$次(包括$0$和$K$)以下操作。
- 交换$S$中相邻的两个字符。
操作后$S$中连续的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
交换第6个和第7个字符,以及第9个和第10个字符后,我们得到YY....YYY..
,其中第7个到第9个位置有三个连续的Y
。
我们无法有四个或更多的连续Y
,所以答案是$3$。
样例输入 2
YYYY....YYY 3
样例输出 2
4