Problem:


Score : 400 points

Problem Statement

There are N people standing in a queue from west to east.

Given is a string S of length N representing the directions of the people.
The i-th person from the west is facing west if the i-th character of S is L, and east if that character of S is R.

A person is happy if the person in front of him/her is facing the same direction.
If no person is standing in front of a person, however, he/she is not happy.

You can perform the following operation any number of times between 0 and K (inclusive):

Operation: Choose integers l and r such that 1 \leq l \leq r \leq N, and rotate by 180 degrees the part of the queue: the l-th, (l+1)-th, ..., r-th persons. That is, for each i = 0, 1, ..., r-l, the (l + i)-th person from the west will stand the (r - i)-th from the west after the operation, facing east if he/she is facing west now, and vice versa.

What is the maximum possible number of happy people you can have?

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

|S| = N

Each character of S is L or R.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of happy people after at most K operations.

Sample Input 1

6 1
LRLRRL

Sample Output 1

3

If we choose (l, r) = (2, 5), we have LLLRLL, where the 2-nd, 3-rd, and 6-th persons from the west are happy.

Sample Input 2

13 3
LRRLRLRRLRLLR

Sample Output 2

9

Sample Input 3

10 1
LLLLLRRRRR

Sample Output 3

9

Sample Input 4

9 2
RRRLRLRLL

Sample Output 4

7



Sample input:
6 1
LRLRRL


Sample output:
3

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(input()+"X")

temp = S[0]
cnt = 1
c_cnt = 1
ans = 0

for i in range(1, N+1):
  if temp == S[i]:
    cnt += 1
  else:
    ans += cnt - 1
    cnt = 1
    c_cnt += 1
    temp = S[i]
  #print(ans, cnt, c_cnt, temp)

#最後の余計な分
c_cnt -= 1

if c_cnt//2 <= K:
  ans += (c_cnt//2) * 2 -1
else:
  ans += K * 2

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(input()+"X")

temp = S[0]
cnt = 1
c_cnt = 1
ans = 0

for i in range(1, N+1):
  if temp == S[i]:
    cnt += 1
  else:
    ans += cnt - 1
    cnt = 1
    c_cnt += 1
    temp = S[i]
  #print(ans, cnt, c_cnt, temp)

#最後の余計な分
c_cnt -= 1

if c_cnt//2 < K:
  ans += (c_cnt//2) * 2
elif c_cnt//2 == K:
  ans += (c_cnt//2) * 2 - 1
else:
  ans += K * 2

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N, K = map(int, input().split())
    S = list(input())
    gr = groupby(S)
    cnt = 0
    happy = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            happy += 1
    for key, group in gr:  # groupはイテレータ。list(group)でリスト化
        """ex.
        0: [0, 0, 0]
        1: [1, 1]
        0: [0, 0, 0]
        1: [1, 1]
        0: [0]
        1: [1]
        """
        cnt += 1
    cut = cnt-1
    while K > 0:
        if cut == 0:
            break
        if cut > 2:
            happy += 2
            cut -= 1
        else:
            happy += 1
            cut -= 1
        K -= 1

    print(happy)

resolve()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N, K = map(int, input().split())
    S = list(input())
    gr = groupby(S)
    cnt = 0
    happy = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            happy += 1
    for key, group in gr:  # groupはイテレータ。list(group)でリスト化
        """ex.
        0: [0, 0, 0]
        1: [1, 1]
        0: [0, 0, 0]
        1: [1, 1]
        0: [0]
        1: [1]
        """
        cnt += 1
    cut = cnt-1
    while K > 0:
        if cut==0: break
        if cut >= 2:
            happy += 2
            cut-=1
        else:
            happy += 1
            cut-=1
        K -= 1

    print(happy)

resolve()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N, K = map(int, input().split())
    S = list(input())
    gr = groupby(S)
    cnt = 0
    happy = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            happy += 1
    for key, group in gr:  # groupはイテレータ。list(group)でリスト化
        """ex.
        0: [0, 0, 0]
        1: [1, 1]
        0: [0, 0, 0]
        1: [1, 1]
        0: [0]
        1: [1]
        """
        cnt += 1
    cut = cnt-1
    while K > 0:
        if cut >= 2:
            happy += 2
            cut-=1
        else:
            happy += 1
        K -= 1

    print(happy)

resolve()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N,K=map(int,input().split())
    S=list(input())
    gr = groupby(S)
    cnt=0
    happy=0
    for i in range(N-1):
        if S[i]==S[i+1]:
            happy+=1
    for key, group in gr: # groupはイテレータ。list(group)でリスト化  
        """ex.
        0: [0, 0, 0]
        1: [1, 1]
        0: [0, 0, 0]
        1: [1, 1]
        0: [0]
        1: [1]
        """
        cnt+=1
    cut=cnt-1
    while K>0:
        if cut>=2:
            happy+=2
        else: happy+=1
        K-=1

        
    print(happy)




    
resolve()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = 0
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1

if K <= m:
    happy += 2*K
else:
    if m > 1:
        happy += 2*m
    elif S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = 0
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1

if K <= m:
    happy += 2*K
else:
    happy += 2*m
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = -1
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1
m = max(m, 0)

if K <= m:
    happy += 2*K
else:
    happy += 2*m
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = 0
for i in range(1, N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1

if K <= m:
    happy += 2*K
else:
    happy += 2*(m-1)
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = -1
for i in range(1, N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1
m = max(m, 0)

if K <= m:
    happy += 2*K
else:
    happy += 2*m
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = 0
for i in range(1, N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1

if K <= m:
    happy += 2*K
else:
    happy += 2*m
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

happy = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        happy += 1

m = 0
for i in range(1, N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        m += 1

if K <= m:
    happy += 2*K
else:
    happy += 2*m + 1
print(happy)

Submission status: Wrong Answer

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    s = list(input())

    cnt = 0
    happy = 0
    for i in range(1, n):
        if s[i - 1] != s[i]:
            cnt += 1
        else:
            happy += 1

    kaisu = cnt // 2
    happy_max = max(1, cnt - 1)

    ans = min(2 * k, happy_max)
    print(ans + happy)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

N, K = map(int, input().split())
S = input()

s = S[0]
count = 0
k = 0
for i in range(1, len(S)):
    #print(S[i], s)
    if s == S[i]:
        count += 1
    else:
        s = S[i]
        k += 1
        
count += K * 2
if K == k // 2 + 1:
    count -= 1
print(count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()

s = S[0]
count = 0
k = 0
for i in range(1, len(S)):
    #print(S[i], s)
    if s == S[i]:
        count += 1
    else:
        s = S[i]
        k += 1
        
if K > k:
    count += k * 2
elif K < k:
    count += K * 2
else:
    count += K * 2 - 1
print(count)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, K = getNM()
S = input()
flag = S[0]
sta = 1
lista = []

for i in range(1, N):
    if flag != S[i]:
        # flag(0か1か), sta(どこから続いているか), i(最終的にどこまで続いたか)
        lista.append([flag, sta, i])
        flag = S[i]
        sta = i + 1
lista.append([flag, sta, N])
rang = len(lista)
ans = 0
for i in range(rang):
    opt = lista[min(rang - 1, i + 2 * K + 1)][2] - lista[i][1] + 1 - 2
    ans = max(ans, opt)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = str(input())

def main(N,K,S):
    d1 = [1]
    d2 = []
    flip = True
    for i in range(1, N):
        if S[i] == S[i-1]:
            if flip:
                d1[-1] += 1
            else:
                d2[-1] += 1
        else:
            if flip:
                d2.append(1)
                flip = False
            else:
                d1.append(1)
                flip = True
    if len(d1) == 1 and len(d2) <= 1:
        return N-1
    d1.reverse()
    d2.reverse()
    for i in range(K):
        if len(d1) <= 1 or len(d2) == 0:
            break
        p1 = d1.pop()
        p2 = d1.pop()
        p3 = d2.pop()
        d1.append(p1+p2+p3)
    if len(d1) == 1 and len(d2) <= 1:
        return N-1
    return sum(d1) - len(d1) + sum(d2) - len(d2)
    
    
print(main(N,K,S))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = str(input())

def main(N,K,S):
    d1 = [1]
    d2 = []
    flip = True
    for i in range(1, N):
        if S[i] == S[i-1]:
            if flip:
                d1[-1] += 1
            else:
                d2[-1] += 1
        else:
            if flip:
                d2.append(1)
                flip = False
            else:
                d1.append(1)
                flip = True
    if len(d1) == 1 and len(d2) <= 1:
        return N-1
    d1.reverse()
    d2.reverse()
    for i in range(K):
        if len(d1) <= 1 or len(d2) == 0:
            break
        p1 = d1.pop()
        p2 = d1.pop()
        p3 = d2.pop()
        d1.append(p1+p2+p3)
    return sum(d1) - len(d1) + sum(d2) - len(d2)
    
    
print(main(N,K,S))

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
s = str(input())

cnt = s.count('RL')
ans = 0

for i in range(0,n-1):
    if s[i] != s[i+1]:
        cnt += 1
    else:
        ans += 1


if cnt >= k:
    ans += 2*k
else:
    if k-cnt>=2:
        if s[-1] == 'L' and s[0] == 'L':
            ans += 2
        elif s[-1] == 'L' or s[0] == 'L':
            ans += 1
    else:
        if s[-1] == 'L' or s[0] == 'L':
            ans += 1       


print(min(ans,n-1))

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
s = str(input())

cnt = s.count('RL')
ans = 0

for i in range(0,n-1):
    if s[i] != s[i+1]:
        cnt += 1
    else:
        ans += 1


if cnt >= k:
    ans += 2*k
else:
    if s[-1] == 'L' and s[0] == 'L':
        ans += 2
    elif s[-1] == 'L' or s[0] == 'L':
        ans += 1
        
print(min(ans,n-1))

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = input()
    num = 0
    prev = A[0]
    for a in A[1:]:
        if a == prev:
            if not (a == A[-1] and a == "R"):
                num += 1
        prev = a
    
    print(min(num + 2*K, N - 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = input()
    num = 0
    prev = A[0]
    l = []
    for a in A[1:]:
        if a != prev:
            l.append(a)
        else:
            if not (a == A[-1] and a == "R"):
                num += 1
        prev = a
    for i in range(1, len(l) - 1, 2):
        if K == 0:
            break
        num += 2
        K -= 1

    num += min(2, K)
    print(num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, K = map(int, input().split())
    A = input()
    num = 0
    rls = deque()
    lrs = deque()
    for i in range(len(A)-1):
        s = A[i:i+2]
        if s == "LL" or s == "RR":
            num += 1
        elif s == "RL":
            rls.append(i)
        else:
            lrs.append(i)
    
    if min(len(lrs), len(rls)) == 0 and max(len(lrs), len(rls)) == 1 and K > 0:
        num += 1
    
    while len(lrs) > 0 and len(rls)> 0 and K > 0:
        l = lrs.popleft()
        r = rls.popleft()

        if abs(l - r) != 1:
            num += 2
            K -= 1
        else:
            if len(lrs) == 0 and len(rls) == 0:
                break
            else:
                lrs.append(l)
                rls.append(r)

    print(num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = input()
    num = 0
    rl_num = 0
    lr_num = 0
    for i in range(len(A)-1):
        s = A[i:i+2]
        if s == "LL" or s == "RR":
            num += 1
        elif s == "RL":
            rl_num += 1
        else:
            lr_num += 1 
    
    if ((lr_num == 1 and rl_num == 0) or (lr_num == 0 and rl_num == 1)) and K > 0:
        num += 1
    
    while rl_num > 0 and lr_num > 0 and K > 0:
        num += 2
        rl_num -= 1
        lr_num -= 1
        K -= 1
    print(num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = input()
    num = 0
    rl_num = 0
    lr_num = 0
    for i in range(len(A)-1):
        s = A[i:i+2]
        if s == "LL" or s == "RR":
            num += 1
        elif s == "RL":
            rl_num += 1
        else:
            lr_num += 1 
    
    if (lr_num == 1 and rl_num == 0) or (lr_num == 0 and rl_num == 1) and K > 0:
        num += 1
    
    while rl_num > 0 and lr_num > 0 and K > 0:
        num += 2
        rl_num -= 1
        lr_num -= 1
        K -= 1
    print(num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
inf = 10**15
mod = 10**9+7
n, k = map(int, input().split())
s = input()
count = 0
flag = False
for i,c in enumerate(s):
    if c == 'R':
        if flag == False:
            flag=True
    else:
        if flag == True:
            count+=1
            flag=False
if flag == True and count > 0:
    count+=1

if k >= count:
    print(n-1)
elif k == count-1:
    if s[0] == 'R' or s[-1] == 'R':
        print(n-2)
    else:
        print(n-3)
else:
    if s[0] == 'R' and s[-1] == 'R':
        print(n - 3 - (count - 2 - k) * 2)
    elif s[0] == 'R' or s[-1] == 'R':
        print(n - 2 - (count - 1 - k) * 2)
    else:
        print(n - 1 - (count - k) * 2)

Submission status: Wrong Answer

Solution code:
inf = 10**15
mod = 10**9+7
n, k = map(int, input().split())
s = input()
cand = 0
count = 0
flag = False
for i,c in enumerate(s):
    if c == 'R':
        if flag == False:
            flag=True
    else:
        if flag == True:
            cand+=2
            count+=1
            flag=False
if flag == True:
    cand+=1
    count+=1
if s[0] == 'R':
    cand-=1

if k >= count:
    print(n-1)
elif k == count-1:
    if s[0] == 'R' or s[-1] == 'R':
        print(n-2)
    else:
        print(n-3)
elif k == count-2:
    if s[0] == 'R' and s[-1] == 'R':
        print(n-3)
    elif s[0] == 'R' or s[-1] == 'R':
        print(n-4)
    else:
        print(n-5)
else:
    if s[0] == 'R' and s[-1] == 'R':
        print(n-3-(count-2-k)*2)
    elif s[0] == 'R' or s[-1] == 'R':
        print(n-2-(count-1-k)*2)
    else:
        print(n-1-(count-k)*2)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
S=list(ns())
LRc=0
hapiness=0
for i in range(N-1):
    if(S[i]=='L' and S[i+1]=='R'):
        LRc+=1
    if((S[i]=='L' and S[i+1]=='L') or (S[i]=='R' and S[i+1]=='R')):
        hapiness+=1

ans=hapiness+min(K,LRc)*2
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	S = inputStr()
	S_tmp = []

	ans = 0
	tmp = ""
	for i,val in enumerate(S):
		if i == 0:
			tmp = val
			S_tmp.append(val)
			continue

		if tmp == val:
			ans += 1
		else:
			S_tmp.append(val)
			tmp = val

	kugiri = len(S_tmp)
	for i,val in enumerate(S_tmp):
		if K == 0:
			break
		K -= 1
		if kugiri == 1:
			break
		elif kugiri == 2:
			kugiri -= 1
			ans += 1
		else:
			kugiri -= 1
			ans += 2

	#print(S_tmp)
	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = list(input())


if len(set(s)) == 1:
    print(len(s) - 1)
    exit()

# print(n, k)
# print(s)

def part(ch='R', rep='L'):
    # repに揃える => chを探す
    listR = []
    i = s.index(ch)
    while i < n:
        j = i
        while j < n and s[j] == ch:
            j += 1
        # print(i, j)
        listR.append((i, j - 1))

        # 末尾は終わり
        if j == n:
            break

        # 末尾以外
        sj = s[j:]
        if ch not in sj:
            break
        i = j + sj.index(ch)

    # k個 or len(listR)だけ取る
    listR = sorted(listR, key=lambda x: x[1] - x[0], reverse=True)
    listR = listR[:min(len(listR), k)]
    # print(listR)

    ss = s[:]
    for (l, r) in listR:
        ss[l:r + 1] = [rep] * (r - l + 1)

    score = 0
    for i in range(n):
        if i == 0:
            if ss[i] == 'R' and ss[i + 1] == ss[i]:
                score += 1
        elif i == n - 1:
            if ss[i] == 'L' and ss[i - 1] == ss[i]:
                score += 1
        else:
            if ss[i] == 'L':
                if ss[i - 1] == ss[i]:
                    score += 1
            else:
                if ss[i + 1] == ss[i]:
                    score += 1
    return score

s1 = part('R', 'L')
s2 = part('L', 'R')
print(max(s1, s2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, K = [int(s) for s in input().split()]
S = input()
state = 0
diff_cnt_total = 0

if S[0] == 'R':
    check_word = 'RLR'
else:
    check_word = 'LRL'

s_index = 0
e_index = 3

while(e_index <= N):
    if S[s_index:e_index] == check_word:
        diff_cnt_total += 1
        s_index += 3
        e_index += 3
    else:
        s_index += 1
        e_index += 1

if S[(N-3):N] != check_word and S[N-2] != S[N-1]:
    diff_cnt_total += 1

print(N - diff_cnt_total - 1)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
s = input()
n_group = 0
now = s[0]
cnt = 0
happy = 0
s += 'z'
for i in s:
	if now != i:
		n_group += 1
		if cnt > 1:
			happy += cnt - 1
		cnt = 1
	else:
		cnt += 1
	now = i

for i in range(k):
	if n_group > 2:
		n_group -= 2
		happy += 2
	else:
		happy += 1
print (happy)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())

S = input()
count = 0

inside = []
happy = 0
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        happy += 1
    if S[i] == 'R' and S[i+1] ==  'L':
        inside.append((i,i+1))

happy += 2*(min(K,len(inside)))
if K - len(inside) > 0:
  if S[N-1] == 'R':
    happy += 1
print(happy)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    s = list(input())
    count = []
    for i in range(n):
        if i == 0:
            count.append([s[i], 1])
        elif s[i] == count[-1][0]:
            count[-1][1] += 1
        else:
            count.append([s[i], 1])
    answer = 0
    reverse = {"L": "R", "R": "L"}
    change = 0
    last_seen = 0
    for i in range(1, len(count), 2):
        if k <= change:
            break
        else:
            count[i][0] = reverse[count[i][0]]
            change += 1
            last_seen = i
    for i in range(len(count)):
        if count[i][0] == count[0][0]:
            answer += count[i][1]
        else:
            break
    if last_seen + 1 == len(count):
        answer -= 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n-1)
elif n == 1:
    print(0)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    #print(happy)
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    #print(rl, lr)
    min_rllr = min(rl, lr)
    max_rllr = max(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2 + (max_rllr-min_rllr)
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n-1)
elif n == 1:
    print(0)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    #print(happy)
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    #print(rl, lr)
    min_rllr = min(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n-1)
elif n == 1:
    print(0)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    print(happy)
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    print(rl, lr)
    min_rllr = min(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n-1)
elif n == 1:
    print(0)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    print(happy)
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    print(rl, lr)
    min_rllr = min(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2 + (max(rl, lr) - min_rllr)
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n-1)
elif n == 1:
    print(0)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    min_rllr = min(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k = map(int, input().split())
s = input()
right = s.count("R")
left = s.count("L")

if min(right, left) <= k:
    print(n)
else:
    # 操作前の幸福な人の数を調べる
    happy = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            happy += 1
    # RL...LR,LR...RLを数える
    rl = s.count("RL")
    lr = s.count("LR")
    min_rllr = min(rl, lr)
    if rl != 0 and lr != 0:
        if k >= min_rllr:
            happy += min_rllr*2
        else:
            happy += k*2
    else:
        happy += k
    print(happy)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

n, k = map(int, input().split())

D = {
    'L': 0,
    'R': 0
}

for val, it in groupby(input()):
    D[val] += 1

if D['L'] == D['R']:
    u = 2 * max([0, D['L'] - k]) + (D['L'] - k == 0)
else:
    u = 1 + 2 * max([0, min(D.values()) - k])

print(n - u)