分数: 400 点
问题陈述
有 N 人们从西向东排队。
给定的是一个字符串 S 长度 N 代表人民的方向。
的 i- 从西边的第一个人面朝西,如果 i- 第一个字符 S is L,如果该字符为东 S is R.
如果一个人面前的人面向同一个方向,他/她就会感到幸福。 然而,如果没有人站在一个人面前,他/她就会不高兴。
您可以执行以下操作任意次数 0 和 K (含):
操作:选择整数 l 和 r 这样 1 \leq l \leq r \leq N,并旋转 180 度队列的部分: l-th, (l+1)-th, ..., r第人。也就是说,对于每个 i = 0, 1, ..., r-l, (l + i)- 第一个来自西方的人将站在 (r - i)- 操作后从西数第一个,如果他/她现在面向西,则面向东,反之亦然。
你最多可以拥有多少个快乐的人?
约束
- N 是满足以下条件的整数 1 \leq N \leq 10^5.
- K 是满足以下条件的整数 1 \leq K \leq 10^5.
- |S| = N
- 每个字符 S is
LorR.
输入
输入由标准输入按以下格式给出:
N K S
输出
打印最多之后快乐的人的最大数量 K 操作。
示例输入 1
6 1 LRLRRL
示例输出 1
3
如果我们选择 (l, r) = (2, 5),我们有 LLLRLL,其中 2-nd, 3-rd,和 6第一个西方人很高兴。
示例输入 2
13 3 LRRLRLRRLRLLR
示例输出 2
9
示例输入 3
10 1 LLLLLRRRRR
示例输出 3
9
示例输入 4
9 2 RRRLRLRLL
示例输出 4
7