← 返回题目列表

AtCoder · arc157_b

B. XYYYX序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个字符串 S 长度 N 组成 X 和 Y。 你会选择 K 字符位于不同位置 S 并更改其中每一个: X 变为 Y 和 Y 变为 X。 找出连续的最大可能对数 结果字符串中包含 Y。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N
  • S 是一个长度为的字符串 N 组成 X 和 Y.

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印最大可能的连续对数 Y。


示例输入 1

5 1
XYXYX

示例输出 1

2

您将选择一个角色。

  • 如果您选择 1-st 字符,结果字符串是 YYXYX,一对连续 Y位于位置 1, 2.
  • 如果您选择 2-nd 字符,结果字符串是 XXXYX,没有一对连续的 Ys。
  • 如果您选择 3-rd 字符,结果字符串为 XYYYX,有两对连续 Y位于位置 2, 3 和 3, 4.
  • 如果您选择 4- 第一个字符,结果字符串是 XYXXX,没有一对连续的 Ys。
  • 如果您选择 5- 第一个字符,结果字符串是 XYXYY,一对连续 Y位于位置 4, 5.

因此,寻求的最大数量是 2.


示例输入 2

5 4
XYXYX

示例输出 2

2

最好选择 1-st, 2-nd, 3-rd,和 5要获取的第个字符 YXYYY,或选择 1-st, 3-rd, 4-th,以及 5要获取的第个字符 YYYXY。 请注意,您不能多次选择同一位置的角色。