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: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
r = []
l = []
cnt1 = 0
cnt2 = 0

p = 0
if 'L' == S[0]:
    for i in range(N):
        if 'L' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            l.append(p)
            break
else:
    for i in range(N):
        if 'R' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            r.append(p)
            break

ans = [1]
for i in range(ind, N):
    if S[i] == 'L':
        if cnt2:
            r.append(cnt2)
            ans.append(2)
            cnt2 = 0
        cnt1 += 1
    else:
        if cnt1:
            l.append(cnt1)
            ans.append(2)
            cnt1 = 0
        cnt2 += 1
if cnt1:
    ans.append(1)
else:
    ans.append(1)

ans.sort()
ans.reverse()

sums = 0
for i in range(N-2):
    if 'LL' == S[i:i+2]:
        sums += 1
    elif 'RR' == S[i:i+2]:
        sums += 1
#print(sums)
if K >= len(ans):
    print(len(S) - 1)
else:
    if sums + sum(ans[:K]) >= len(S):
        print(len(S) - 1)
    else:
        print(sums + sum(ans[:K]))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
r = []
l = []

a = ""
count = 1

for i in range(n - 1):
    t = i + 1
    if s[t] == s[t - 1]:
        count += 1
    else:
        if s[t - 1] == "L":
            l.append(count)
        else:
            r.append(count)
        count = 1

if s[n - 2] == s[n - 1]:
    if s[n - 1] == "L":
        l.append(count)
    else:
        r.append(count)
else:
    if s[n - 1] == "L":
        l.append(1)
    else:
        r.append(1)

r.sort()
l.sort()

for i in range(k):
    r.pop(-1)
    l.pop(-1)

if len(r) < len(l):
    if len(r) == 0:
        ans = n - 1
    else:
        ans = n - 1 - len(r) - 1
else:
    if len(l) == 0:
        ans = n - 1
    else:
        ans = n - 1 - len(l) - 1

print(ans)

Submission status: Runtime Error

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

    l = []
    r = []
    ll = 0
    for i in range(n):
        if s[i] == "L":
            ll += 1
        else:
            if ll > 0:
                l.append([ll, i-ll])
                ll = 0
    if s[i - 1] == "L":
        l.append([ll, i-ll+1])
    rr = 0
    for i in range(n):
        if s[i] == "R":
            rr += 1
        else:
            if rr > 0:
                r.append([rr, i-rr])
                rr = 0
    if s[i - 1] == "R":
        r.append([rr, i-rr+1])

    #l = sorted(l, key=lambda x: x[1], reverse=False)
    #r = sorted(r, key=lambda x: x[1], reverse=True)
    l = sorted(l)
    r = sorted(r, reverse=True)

    #print(l, r)

    import copy
    ss = copy.deepcopy(s)
    for i in range(k):
        for j in range(l[i][0]):
            ss[l[i][1] + j] = "R"
    ansa = 0
    for i in range(n-1):
        if ss[i] == ss[i + 1]:  # and ss[i] == "R":
            ansa += 1
   # print(ans, ss)

    for i in range(k):
        for j in range(r[i][0]):
            s[r[i][1] + j] = "L"
    ansb = 0
    for i in range(n-1):
        if s[i] == s[i + 1]:  # and s[i] == "L":
            ansb += 1
    #print(ans, s)
    print(max(ansa, ansb))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
n,k = map(int,input().split())
s = input()
ans = 0
count = 0
for i in range(1,n-1):
    if s[i] == "L" and s[i-1] == "L":
        ans += 1
    elif s[i] == "R" and s[i+1] == "R":
        ans += 1
    if s[i] == "R" and s[i+1] == "L":
        count += 1
    elif s[i] == "L" and s[i+1] == "R":
        count += 1
        
if s[0] == "R" and s[1] == "R":
    ans += 1
if s[-1] == "L" and s[-2] == "L":
    ans += 1
        
while k > 0:
  if count > 1:
    ans += 2
    count -= 2
  elif count == 1:
    ans += 1
    count -= 1
  k -= 1
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
r = []
l = []
cnt1 = 0
cnt2 = 0

p = 0
if 'L' == S[0]:
    for i in range(N):
        if 'L' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            l.append(p)
            break
else:
    for i in range(N):
        if 'R' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            r.append(p)
            break

ans = [1]
for i in range(ind, N):
    if S[i] == 'L':
        if cnt2:
            r.append(cnt2)
            ans.append(2)
            cnt2 = 0
        cnt1 += 1
    else:
        if cnt1:
            l.append(cnt1)
            ans.append(2)
            cnt1 = 0
        cnt2 += 1
if cnt1:
    ans.append(1)
else:
    ans.append(1)

ans.sort()
ans.reverse()

sums = 0
for i in range(N):
    if 'LL' == S[i:i+2]:
        sums += 1
    elif 'RR' == S[i:i+2]:
        sums += 1
#print(sums)
if K >= len(ans):
    print(len(S) - 1)
else:
    if sums + sum(ans[:K]) >= len(S):
        print(len(S) - 1)
    else:
        print(sums + sum(ans[:K]))

Submission status: Runtime Error

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

def count_diff(a,b):
    cnt = 0
    for c1,c2 in zip(a, b):
        if c1 != c2:
            cnt += 1
    return cnt

s2 = s[1:]
cnt = count_diff(s[:-1], s2)
init = n - cnt - 1

if s[0] == "L" and s[1] == "L":
    if s[-1] == "R" and s[-2] == "R":
        init -= 1

print(init + (2 * k))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = list(input())
while k > 0:
    for i in range(n):
        s[i], s[(n-1)-i] = s[(n-1)-i], s[i]
        if s[i] == 'L':
            s[i] = 'R'
        else:
            s[i] = 'L'
        if s[(n-1)-i] == 'L':
            s[(n-1)-i] = 'R'
        else:
            s[(n-1)-i] = 'L'
        if s[i] == s[i+1]:
            k -= 1
            if k == 0:
                break
        else:
            s[i], s[(n-1)-i] = s[(n-1)-i], s[i]
pt = 0
for i in range(n):
    if i != n-1:
        if s[i] == s[i+1]:
            pt += 1
print(pt)

Submission status: Runtime Error

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



left=(msg[0]!="R")
right=(msg[-1]!="L")
msg2=msg[1:-1]
cntrl=msg.count("RL")


first=n-cntrl*2-left-right
print("f",first)
ans=first+2*min(k,msg2(count("RL")))
if ans==n:
  ans=n-1
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#ABC140 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
s = list(input())
l = []
cnt = 1
for i in range(1,n):
    if s[i-1] != s[i]:
        l.append((cnt,i-1))
        cnt = 0
    cnt += 1
l.append((cnt,i))
m = len(l)
h = []
for i in range(m):
    if i == 0:
        heappush(h,(-(l[i][0]+l[i+1][0]),l[i][0],l[i][1]))
    elif i == m-1:
        heappush(h,(-(l[i][0] + l[i-1][0]),l[i][0],l[i][1]))
    else:
        heappush(h,(-(l[i][0] + l[i-1][0] + l[i+1][0]),l[i][0],l[i][1]))
for _ in range(min(k,len(h))):
    l,i,j = heappop(h)
    if s[j] ==  'R':
        s[j-i+1:j+1] = 'L'*i
    else:
        s[j-i+1:j+1] = 'R'*i
ans = 0
for i in range(n):
    if s[i] == 'L':
        if i > 0:
            if s[i-1] == 'L':
                ans += 1
    else:
        if i < n-1:
            if s[i+1] == 'R':
                ans += 1
print(ans)

Submission status: Runtime Error

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

largest = 0
largest_left_index = -1

sum_list = list()

count = 0
for i in range(N):
    if S[i] == "L":
        if count <= 0:
            count = count - 1
        else:
            sum_list.append(count)
            count = -1
    elif S[i] == "R":
        if count >= 0:
            count = count + 1
        else:
            sum_list.append(-count)
            count = 1
else:
    sum_list.append(count) if count > 0 else sum_list.append(-count)

length = len(sum_list)
current_max = 0
current_max_index = 0
for j in range(length):
    current_sum = sum_list[j]
    if j < length - 1:
        current_sum = current_sum + sum_list[j+1]
    if j < length - 2:
        current_sum = current_sum + sum_list[j+2]

    if current_sum > current_max:
        current_max = current_sum
        current_max_index = j

if current_max_index < length - 2:
    sum_list.pop(current_max_index + 2)
if current_max_index < length - 1:
    sum_list.pop(current_max_index + 1)
sum_list.pop(current_max_index)
sum_list.insert(current_max_index, current_max)

for i in range(K-1):
    left = sum_list[current_max_index]
    if current_max_index > 1:
        left = left + sum_list[current_max_index - 1]
    if current_max_index > 2:
        left = left + sum_list[current_max_index - 2]

    right = sum_list[current_max_index]
    if current_max_index < len(sum_list) - 1:
        right = right + sum_list[current_max_index + 1]
    if current_max_index < len(sum_list) - 2:
        right = right + sum_list[current_max_index + 2]

    if left >= right:
        sum_list.pop(current_max_index)
        sum_list.insert(current_max_index, left)
        if current_max_index > 1:
            sum_list.pop(current_max_index - 1)
        if current_max_index > 2:
            sum_list.pop(current_max_index - 2)
    else:
        length = len(sum_list)
        if current_max_index < length - 2:
            sum_list.pop(current_max_index + 2)
        if current_max_index < length - 1:
            sum_list.pop(current_max_index + 1)
        sum_list.pop(current_max_index)
        sum_list.insert(current_max_index, right)

res = 0
for i in range(len(sum_list)):
    res = res + sum_list[i] - 1

print(res)

Submission status: Runtime Error

Solution code:
if K<N//2+1:
    for i in range(K):
        flag=0
        old=S[0]
        reverse=[]

        for j in range(1,N):
    #         print(j,old,S[j])
            if S[j]!=old:
                reverse.append(j)
                old=S[j]

            if len(reverse)==2:

                for k in range(reverse[0],reverse[1]):

                    if S[k]=='R':
                        S[k]='L'
                    else:
                        S[k]='R'
                break

        if len(reverse)==1:
                 for k in range(reverse[0],N):
                    if S[k]=='R':
                        S[k]='L'
                    else:
                        S[k]='R'
    old='aaa'
    ans=0
    for s in S:
        if old==s:
            ans+=1
        old=s
    print(ans)
else:
    print(N)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
S = list(input())
rS = S[::-1]
R = 0
L = 0
for i in range(N-1):
    if S[i]==S[i+1] == 'R':
        R+=1
    else:
        pass
for i in range(N-1):
    if rS[i]==rS[i+1] == 'L':
        L+=1
    else:
        pass
q = R + L
ks=0
x = 0
for i in range(N-1):
    if ks ==K:
        break
    elif S[i+x] == S[i+x+1]:
        pass
    elif S[i+x] != S[i+x+1]:
        q += 1
        ks += 1
        for l in range(N-i+x-2):
            if i+x+1+l==N-1:
                x=l+1
                break
            elif S[i+x+1+l] == S [i+x+l+2]:
                pass
            else:
                x=l+1
                q += 1
            break
print(q)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    n,k=map(int,input().split())
    s=input()
    b=[]
    for i in range(n):
        b.append(1 if s[i]=="R" else 0)
#    print(b)
    kohuku=0

    if b.count(0)>n//2:
        h=1
    else:
        h=0

    a=[]
    temp=0
#    print(a,n//2,h)
    for i in range(n):
        if b[i]==h:
            temp+=1
#            if i==0 or i==n:
#                temp-=0.5
        else:
            a.append([temp,i])
            temp=0
    a=sorted(a,reverse=True)

#    print(a)
    for i in range(k):

        for l in range(a[i][1]-a[i][0],a[i][1]):
            b[l]=-(h-1)
#    print(b)
    for i in range(1,n):
        if b[i]==1 and b[i-1]==1:
            kohuku+=1
        if b[i]==0 and b[i-1]==0:
            kohuku+=1

    print(kohuku)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k =map(int, input().split()) 
s = input()
count = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        count += 1
print(str(count+k*2)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
count = 0
s = 'X' + s + 'X'
for i in range(1, n+1):
    print(f's[i]: {s[i]} s[i-1]: {s[i-1]} s[i+1]:{s[i+1]}')
    if (s[i] == s[i-1] and s[i] == 'L') or \
        (s[i] == s[i+1] and s[i] == 'R'):
        count += 1
if count == n-2:
    print(count + 1)
else:
    print(count + 2*k)

Submission status: Runtime Error

Solution code:
n, k = (int(x) for x in input().split())
s = input()
happy = 0

if(s[0] == 'R' and s[1] == 'R'):
    happy = happy + 1
if(s[-1] == 'L' and s[-2] == 'L'):
    happy = happy + 1

for i in range(1,n-1):
    if(s[i] == 'R' and s[i+1] == 'R'):
        happy = happy + 1
    if(s[i] == 'L' and s[i-1] == 'L'):
        happy = happy + 1

happy = happy + 2*k
print(min(happy, n-1))

Submission status: Runtime Error

Solution code:
# sys.stdin.readline
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        S = input().rstrip()

        b = []
        before = S[0]
        cnt = 1
        for i in range(1, N):
            if before == S[i]:
                cnt += 1
                if i == N - 1:
                    b.append(cnt)
            else:
                b.append(cnt)
                cnt = 1
                before = S[i]

        for _ in range(K):
            target = None
            tmp = 0
            if len(b) == 1:
                break
            if len(b) == 2:
                b = [sum(b)]
                break
            for i in range(1, len(b) - 1):
                current = b[i - 1] + b[i] + b[i + 1]
                if current > tmp:
                    tmp = current
                    target = i
            b = b[:target - 1] + [tmp] + b[target + 2:]

        print(sum(b) - len(b))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Runtime Error

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

S = list(input())
m = 0
for i in range(k):
    for c in range(len(S)):
        if S[c] == "R":
            S[c] = "L"
            while(S[c] != "R"):
                c += 1
                if  c == len(S)-1:
                    break
                if S[c] =="R":
                    S[c] = "L"
                else:
                    S[c] = "R"
            break
    if m < S.count("L"):
        m = S.count("L")
print(m)

Submission status: Runtime Error

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

    # print("N,K",N,K)
    # print("S",S)
    result =0
    for i in range (K):
        for i in range(N-2):
            if S[i]==S[i+2]!=S[i+1]:
                # print("change it->",i+1)
                S[i+1]=S[i]
                break
        else:
            if S[0]!=S[1]:
                S[0]=S[2]
            elif S[-1]!=S[-2]:
                S[-1]=S[-3]

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

if __name__ =="__main__":
    main()


# 13 3
# LRRRRRRRRRLLR

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = str(input())
max = N-1
cnt = 0

if (S[0] == "R") & (S[1] == "R"):
    cnt += 1
if (S[N-1] =="L") & (S[N-2]=="L"):
    cnt += 1
for i in range(1, N-1):
    if S[i] == "L":
        if S[i-1] == "L":
            cnt += 1
    if S[i] == "R":
        if S[i+1] == "R":
            cnt += 1

if (cnt + K*2) > max:
    print(max)
else:
    print(cnt + K*2)

Submission status: Runtime Error

Solution code:
n,k= map(int,(input().split()))
b= input()
LRn=len(re.findall('LR',b))
RLn=len(re.findall('RL',b))

if min(LRn,RLn)>=k:
    ans=k*2
elif min(LRn,RLn)<=k and max(LRn,RLn)>=k:
    ans=k+min(LRn,RLn)
else:
    ans=LRn+RLn

a= list(b)
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        ans +=1

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
from pprint import pprint
N, K  = map(int,input().split())
S = input()

same_L_cnt = 0

up_cnt = 0
same_cnt = 0
before = ""
st = 0
ed = 0


    
for i in range(N):
    now_S = S[i]
    if now_S == 'L':
        now_S = 1
    else:
        now_S = 0
    # 前回と同じか確認
    if now_S == before:
        # 同じならカウントアップ
        same_cnt += 1
    # L R R ..... R Lが出現したか確認する
    buf.append(now_S)
    #print('------ buffer ------')
    #pprint(buf)
    #print('--------------------')
    if buf[0] != 1:
        buf = []
    elif len(buf) == 2 and buf[1] == 1:
        buf = [1]
    elif len(buf) < 3:
        pass
    else:
        t = buf[1:len(buf)-2]
        if sum(t) != 0:
            buf = []
        elif buf[len(buf)-1] == 1:
            up_cnt += 1
            buf = [1]
        else:
            pass
    before = now_S
#print(up_cnt)
#print(same_cnt)

# 右端パターン 
up_R_flg = 0
if sum(buf) == 1:
    up_R_flg = 1
# 右端パターン
# 右端Rで一回でもLが出ていれば+1できる
up_L_flg = 0
if S[0] == "R" and same_cnt != N-1:
    up_L_flg = 1

pt = same_cnt
rev_cnt = min(K , up_cnt)
remain_cnt = K - rev_cnt
extra = 0
if up_R_flg and remain_cnt > 0:
    extra += 1
    remain_cnt -= 1
if up_L_flg and remain_cnt > 0:
    extra += 1
print(same_cnt + rev_cnt * 2 + extra)

Submission status: Runtime Error

Solution code:
import re

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

LL = re.finditer('L{1,}', S)
RR = re.finditer('R{1,}', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l[0]) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r[0]) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])


print(happy)

Submission status: Runtime Error

Solution code:
import re

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

LL = re.finditer(r'L{1,}', S)
RR = re.finditer(r'R{1,}', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l[0]) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r[0]) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])


print(happy)

Submission status: Runtime Error

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

same_L_cnt = 0

up_cnt = 0
same_cnt = 0
before = ""
buf = []


    
for i in range(N):
    now_S = S[i]
    if now_S == 'L':
        now_S = 1
    else:
        now_S = 0
    # 前回と同じか確認
    if now_S == before:
        # 同じならカウントアップ
        same_cnt += 1
    # L R R ..... R Lが出現したか確認する
    buf.append(now_S)
    #print('------ buffer ------')
    #pprint(buf)
    #print('--------------------')
    if buf[0] != 1:
        buf = []
    elif len(buf) == 2 and buf[1] == 1:
        buf = [1]
    elif len(buf) < 3:
        pass
    else:
        t = buf[1:len(buf)-2]
        if sum(t) != 0:
            buf = []
        elif buf[len(buf)-1] == 1:
            up_cnt += 1
            buf = [1]
        else:
            pass
    before = now_S
#print(up_cnt)
#print(same_cnt)

# 右端パターン 
up_R_flg = 0
if sum(buf) == 1:
    up_R_flg = 1
# 右端パターン
# 右端Rで一回でもLが出ていれば+1できる
if S[0] == "R" and same_cnt != N-1:
    up_L_flg = 1

pt = same_cnt
rev_cnt = min(K , up_cnt)
remain_cnt = K - rev_cnt
extra = 0
if up_R_flg and remain_cnt > 0:
    extra += 1
    remain_cnt -= 1
if up_L_flg and remain_cnt > 0:
    extra += 1
print(same_cnt + rev_cnt * 2 + extra)

Submission status: Runtime Error

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

check=s[0]
right=0
left=0
for i in range(1,n):
    if s[i]==check and check=='R':
        right+=1
    elif s[i]==check and check=='L':
        left+=1
    check = s[i]
check2=s[0]
renzokul=0
renzokur=0

for i in range(1,n-1):
    if s[i-1]==s[i] and s[i]==s[i+1] and s[i]=='L':
        renzokul+=1
    if s[i-1]==s[i] and s[i]==s[i+1] and s[i]=='R':
        renzokur+=1
if renzokul!=0:
    renzokul+=2
if renzokur!=0:
    renzokur+=2
    
renzoku=renzokul+renzokur    
ans =n-right-left


hashi=0
if s[0]!=s[1]:
    hashi+=1
if s[-1]!=s[-2]:
    hashi+=1
    
n-renzoku#koritu

while k>0:
    if n-renzoku-hashi>=1:
        ans-=2
        renzoku+=2
    elif n-renzoku-hashi<1 and n-renzoku>=1:
        ans-=2        
    k-=1
    
print(min(n,n-ans))

Submission status: Runtime Error

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

arr = list(input())

for _ in range(k):
    whl = [i for i, x in enumerate(arr) if x == 'L']
    whr = [i for i, x in enumerate(arr) if x == 'R']
    a=[]
    for i in range(1,len(whl)):
        a.append(whl[i]-whl[i-1])
    
    b=[]
    for i in range(1,len(whr)):
        b.append(whr[i]-whr[i-1])
    
    suma = []
    for i in range(len(a)-1):
        suma.append(a[i]+a[i+1])
    
    sumb = []
    for i in range(len(b)-1):
        sumb.append(b[i]+b[i+1])
    
    
    
    if max(suma) > max(sumb):
        na = suma.index(max(suma))
        
        arr[whl[na]+1:whl[na+2]] = arr[whl[na]+1:whl[na+2]][::-1]
        for i in range(whl[na]+1,whl[na+2]):
            if arr[i] == "L":
                arr[i] = "R"
            else:
                arr[i] = "L"

    
    else:
        nb = sumb.index(max(sumb))
        
        arr[whr[nb]+1:whr[nb+2]-1] = arr[whr[nb]+1:whr[nb+2]-1][::-1]
        for i in range(whr[nb]+1,whr[nb+2]):
            if arr[i] == "L":
                arr[i] = "R"
            else:
                arr[i] = "L"

count = 0
for i in range(len(arr)-1):
    if arr[i]==arr[i+1]:
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
def d_face_produces_unhappiness():
    N, K = [int(i) for i in input().split()]
    S = input()
    before_char = S[0]
    t = []
    v = 0
    for s in S + '*':
        if s != before_char:
            t.append(v)
            v = 1
        else:
            v += 1
        before_char = s
    t.sort(reverse=True)
    for i in range(K):
        t[i] += 2
    return min(sum([e - 1 for e in t]), N - 1)

print(d_face_produces_unhappiness())

Submission status: Runtime Error

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

sl = 0
for i in range(N-1, -1, -1):
    if S[i] == S[0]:
        sr = i
        break
    else:
        sl += 1
if sl == 0:
    sl = 1
r = sr
l = 0
change = 0
while l<=r and change <= K:
    if S[l] != S[l+1]:
        if S[r] != S[r-1]:
            change += 1
            l += 1
            r -= 1
        else:
            r -= 1
    else:
        l += 1
if change < K:
    ans = N-1
else:
    if r < l:
        ans = sr + sl-1
    else:
        ans = l-1 + (sr-r-1) + sl-1
        for i in range(l, r):
            if S[i] == S[i+1]:
                ans += 1
print(ans)

Submission status: Runtime Error

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

res = 0
pre = None
add = {2: 0}
if S[0] == S[-1] and S[0] == "L":
    add[0] = 1
else:
    add[0] = 0
for s in S:
    if pre is None:
        pass
    elif pre == s:
        res += 1
    elif pre == "R":
        add[2] += 1
    pre = s

if add[2] > K:
    res += 2 * K
    print(res)
else:
    res += 2 * add[2]
    K -= add[2]
    if K > 0:
        res += add[1]
    print(res)

Submission status: Runtime Error

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

res = 0
pre = None
add = {2: 0}
if S[0] == S[-1] and S[0] == "L":
    add[0] = 1

for s in S:
    if pre is None:
        pass
    elif pre == s:
        res += 1
    elif pre == "R":
        add[2] += 1
    pre = s

if add[2] > K:
    res += 2 * K
    print(res)
else:
    res += 2 * add[2]
    K -= add[2]
    if K > 0:
        res += add[1]
    print(res)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
max_happy = N-1
init_happy = 0
for i in range(1, N-1):
  if S[i]=="L" and S[i-1]=="L":
    init_happy += 1
  elif S[i]=="R" and S[i+1]=="R":
    init_happy += 1

if S[0]=="R" and S[1]=="R":
  init_happy += 1

if S[-1]=="L" and S[-2]=="L":
  init_happy += 1

ans = min(max_happy, init_happy+K*2)

print(ans)

Submission status: Runtime Error

Solution code:
n=list(map(int,input().split()))
s=input()
a,b,c=[],s[0],0
if n[0]==1:
    print('0')
for i in range(n[0]-1):
    if b==s[i+1]:
        c+=1
    else:
        a.append(c)
        c=0
    b=s[i+1]
if c!=0:
    a.append(c)
if s[-2]==s[-1]:
    a[-1]+=1
else:
    a.append(1)
if n[1]>=len(a)//2:
    print(n[0]-1)
else:
    print(sum(a)+2*n[1]-1)

Submission status: Runtime Error

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

count = 1
for i in range(1, n):
    if s[i] == s[i-1]:
        count += 1
    else:
        if s[i-1] == "L":
            a.append(count)
        else:
            b.append(count)
        count = 1
if s[i] == "L":
    a.append(count)
else:
    b.append(count)
count = 1

a.sort(reverse=True)
b.sort(reverse=True)
ans1 = sum(a) - len(a)
ans2 = sum(b) - len(b)
for i in range(min(2*k, len(b))):
    ans1 += b[i]
if len(b) < 2*k:
    ans1 += 2*k - len(b)
ans1 = min(n-1, ans1)
for i in range(min(2*k, len(a))):
    ans2 += a[i]
if len(a) < 2*k:
    ans2 += 2*k - len(a)
ans2 = min(n-1, ans2)
print(max(ans1, ans2))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(n**3)
    return

#B
def B():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    ans = sum(b)
    for i in range(n-1):
        x = a[i]
        y = a[i+1]
        if y == x+1:
            ans += c[x-1]
    print(ans)
    return

#C
def C():
    n = I()
    b = LI()
    b.append(float("inf"))
    a = [min(b[i],b[i-1]) for i in range(n)]
    print(sum(a))
    return

#D
def D():
    n,k = LI()
    a = S()
    if a.count("L") in [0,n]:
        print(n-1)
        return
    if n == 1:
        print(0)
        return
    if n == 2:
        print(1)
        return
    ans = 0
    f = [0]*n
    for i in range(n-1):
        if a[i] == a[i+1]:
            ans += 1
            if a[i] == "L":
                f[i+1] = 1
            else:
                f[i] = 1
    f.append(0)
    f.append(0)
    d = defaultdict(lambda : 0)
    l = 0
    s = a[0]
    for i in range(n):
        if a[i] != s:
            d[(l,i-1)] = 1
            s = a[i]
            l = i
    r = n-1
    l = 0
    m = 0
    for i in range(k):
        if not i%2:
            while a[r] != "R":
                r -= 1
            while a[l] != "R":
                l += 1
        else:
            while a[r] != "L":
                r -= 1
            while a[l] != "L":
                l += 1
        if d[(l,r)]:
            print(n-1)
            return
        else:
            m += 2-f[l-1]-f[r+1]
    r = n-1
    l = 0
    m_ = 0
    for i in range(k):
        if i%2:
            while a[r] != "R":
                r -= 1
            while a[l] != "R":
                l += 1
        else:
            while a[r] != "L":
                r -= 1
            while a[l] != "L":
                l += 1
        if d[(l,r)]:
            print(n-1)
            return
        else:
            m_ += 2-f[l-1]-f[r+1]
    print(ans+max(m,m_))
    return

#E
def E():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    p = LI()
    r = [0]*n
    bit = [0]*(n+1)
    for i in range(n)[::-1]:
        r[i] = (n-i-1)-sum(p[i])
        add(p[i])
    print(r)
    l = [0]*n
    bit = [0]*(n+1)
    for i in range(n):
        l[i] = i-sum(p[i])
        add(p[i])
    print(l)

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Runtime Error

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

def change():
    check = S[0]
    k = 1
    while S[k] == check:
        k += 1
    i = 0
    while S[k + i] != check:
        S[k + i] = check
        i += 1

group = 1
old = S[0]
happy_num = 0
for i in range(1, N):
    if old == S[i]:
        group += 1
        if i == N - 1:
            happy_num += group - 1
    else:
        happy_num += group - 1
        old = S[i]
        group = 1
print(happy_num)

border = 0
for k in range(K):
    old = S[0]
    for i in range(1, N):
        if old != S[i]:
            border += 1
            if border == 2:
                break
            old = S[i]
    if border == 0:
        break
    elif border == 1:
        happy_num += 1
        S[1:] = S[0]
    else:
        happy_num += 2
        change()

print(happy_num)