题目描述

给定一个由 X 和 Y 组成、长度为 $N$ 的字符串 $S$。你可以选择 $K$ 个互不相同的位置，将选中的字符进行替换：如果是 X，则替换为 Y；如果是 Y，则替换为 X。请你求出经过替换后，字符串中相邻的 Y 组成的区间最多有多少对。

输入格式

输入以以下格式从标准输入给出。

$N$ $K$ $S$

输出格式

输出经过替换后，字符串中相邻的 Y 组成的区间的最大个数。

样例 1

输入

5 1
XYXYX

输出

2

样例 2

输入

5 4
XYXYX

输出

2

说明/提示

限制条件

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

样例解释 1

只能选择 $1$ 个字符。

• 选择第 $1$ 个字符，替换后字符串为 YYXYX，第 $1,2$ 个字符之间有 $1$ 处 Y 相邻。
• 选择第 $2$ 个字符，替换后字符串为 XXXYX，没有 Y 相邻的地方。
• 选择第 $3$ 个字符，替换后字符串为 XYYYX，第 $2,3$ 和 $3,4$ 个字符之间有 $2$ 处 Y 相邻。
• 选择第 $4$ 个字符，替换后字符串为 XYXXX，没有 Y 相邻的地方。
• 选择第 $5$ 个字符，替换后字符串为 XYXYY，第 $4,5$ 个字符之间有 $1$ 处 Y 相邻。 综上，最大值为 $2$。

样例解释 2

选择第 $1,2,3,5$ 个字符，得到 YXYYY，或者选择第 $1,3,4,5$ 个字符，得到 YYYXY，都是最优方案。 注意不能多次选择同一位置的字符。

由 ChatGPT 4.1 翻译