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())
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)

print(min(first+2*min(cntrl,k),n-1))

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split(' ')))
S = input() + 'Z'
old = ''
ct = 0
cts = []
sums = []
for i in range(len(S)):  # 1e5
    if old != S[i]:
        old = S[i]
        if ct:
            cts.append(ct)
            if not sums:
                sums.append(ct)
            else:
                sums.append(sums[-1] + ct)
        ct = 0
    ct += 1
sums = [0, 0] + sums

ans = -1
lensums = len(sums)
for uragaesu in range(K, K + 1):  # 1e5
    for start in range(N):  # 1e5 / 2 ... TLE?
        if start + 2 * uragaesu + 1 >= lensums:
            break
        ans = max(ans, sums[start + 2 * uragaesu + 1] - sums[start])
    if ans == sums[-1]:
        break
renzoku = (ans if ans >= 0 else sums[-1])
print(renzoku - (renzoku == sums[-1]))

Submission status: Wrong Answer

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

ans = 0
flag = 0

for i in range(n-1):
    if s[i] == s[i+1]:
        ans += 1

for i in range(n-1):
    if s[i] != s[i+1]:
        flag += 1

if k >= flag:
    ans = n-1
elif flag > 1:
    ans += 2*k
else:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
S=input()+'X'
if n==1:
  print(0)
  exit()
if n==2:
  print(1)
  exit()
A=[0]
l=0
r=0
for i in range(n):
  if S[i]=='L':
    l+=1
    if S[i+1]!='L':
      A.append(l)
      l=0
  if S[i]=='R':
    r-=1
    if S[i+1]!='R':
      A.append(r)
      r=0
A=sorted(A)
z=A.index(0)
L=sum(A[z+1:])-len(A[z+1:])-sum(A[:min(z,k)])+min(n-z,k)
R=sum(A[:z])+len(A[:z])-sum(A[-min(n-z,k):])-min(z,k)
if len(A[z+1:])==min(n-z,k):
  L-=1
if len(A[:z])==min(z,k):
  R+=1
print(max(L,-R))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
Slist = []
for k in range(N):
    Slist.append(S[k])
#LR数できまる.
#一番外はRとLをそれぞれ付けて考える
#Lの次にRならLに変えてRが続くならそれもLに返る
ans = 0
count = 0
for i in range(N-1):
    if count == K:
        break
    if Slist[i] == "L" and Slist[i+1] == "R":
        count += 1
        for p in range(i+1,N):
            if Slist[p] == "R":
                Slist[p] = "L"
            else:
                break

for j in range(N-1):
    if Slist[j] == "L" and Slist[j+1]== "R":
        ans += 1

ans = N - 2*ans

if Slist[0] == Slist[-1]:
    ans -= 1

print(ans)

#print(Slist)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
count = 0
s = 'X' + s + 'X'
for i in range(1, n+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)
elif count == n-1:
  	print(count)
else:
    print(count + 2*k)

Submission status: Wrong Answer

Solution code:
import sys
import re
n, k = [int(i) for i in sys.stdin.readline().split()]
s = input()
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
for i in range(k):
    left = min(s.find("LR"), s.find("RL"))
    right = max(s.rfind("RL"), s.rfind("LR"))
    if left == -1 or right == -1:
        cnt += 1
        break
    else:
        cnt += 2
    s = s[left: right]
print(cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


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

    # initialize
    output = 0
    if S[0] == "R" and S[1] == "R":
        output += 1
    for i in range(1, N-1):
        if S[i] == "L":
            if S[i-1] == "L":
                output += 1
        elif S[i] == "R":
            if S[i+1] == "R":
                output += 1
    if S[N-1] == "L" and S[N-2] == "L":
        output += 1

    # reverse count
    k = 0
    i = 0
    while i < N-2:
        if S[i] == S[i+1]:
            i += 1
            continue
        start = S[i]
        # middle = S[i+1]
        for j in range(i+1, N):
            if S[j] == start:
                i = j
                k += 1
                output += 2
                if k == K:
                    return output
                break
            if j == N-1:
                return N - 1


if __name__ == "__main__":
    output = main()
    print(output)

Submission status: Wrong Answer

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

only = True
for s in S:
    if s != S[0]:
        only = False
        break

if only:
    ans = N-1
else:
    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:
        #print('ok!')
        ans = N-1
    else:
        if r < l:
            #print('!!!!!')
            ans = sr + sl-1
        else:
            #print(l-1, sr-r-1, sl-1)
            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: Wrong Answer

Solution code:
import bisect
N, K = list(map(int, input().split()))
S = input().split()[0]

p = 0
lr_index_list = []
rl_index_list = []
for i in range(1, N):
    if S[i] == S[i-1]:
        p += 1
    if S[i-1] + S[i] == 'LR':
        lr_index_list.append(i-1)
    if S[i-1] + S[i] == 'RL':
        rl_index_list.append(i-1)

n_lr = len(lr_index_list)
n_rl = len(rl_index_list)

if n_lr == 0 and n_rl == 0:
    pass
elif n_lr == 1 and n_rl == 0:
    if lr_index_list[0] != 0 and lr_index_list[0] != N - 2:
        # LLLLLRRRRR 系
        p = N - 1
elif n_lr == 0 and n_rl == 1:
    if rl_index_list[0] != 0 and rl_index_list[0] != N - 2:
        # RRRRRLLLLL 系
        p = N - 1
else:
    kouho_n = min(n_lr, n_rl)
    # 少ない方を基準で探す
    if kouho_n == n_lr:
        x_list = lr_index_list
        y_list = rl_index_list
    else:
        x_list = rl_index_list
        y_list = lr_index_list
    c = 0
    for x in x_list:
        y_index = bisect.bisect_left(y_list, x)
        is_ok = False
        # 1個右隣をチェック
        if y_index != len(y_list):
            if abs(y_list[y_index] - x) >= 2:
                is_ok = True
                y_list.remove(y_list[y_index])
        # 1個左隣をチェック
        if is_ok == False and y_index != 0:
            if abs(y_list[y_index-1] - x) >= 2:  # TODO
                is_ok = True
                y_list.remove(y_list[y_index-1])
        # 2個右隣があるかどうかをチェック
        if is_ok == False and y_index + 1 < len(y_list):
            is_ok = True
            y_list.remove(y_list[y_index+1])
        # 2個左隣があるかどうかをチェック
        if is_ok == False and y_index - 2 >= 0:  # TODO
            is_ok = True
            y_list.remove(y_list[y_index-2])
        if is_ok:
            c += 1
        if c >= K:
            break

    p += min(c, K) * 2

ans = p
print(p)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
count = 0
s = 'X' + s + 'X'
for i in range(1, n+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: Wrong Answer

Solution code:
N, K = list(map(int, input().split(' ')))
S = input() + 'Z'
old = ''
ct = 0
cts = []
sums = []
for i in range(len(S)):  # 1e5
    if old != S[i]:
        old = S[i]
        if ct:
            cts.append(ct)
            if not sums:
                sums.append(ct)
            else:
                sums.append(sums[-1] + ct)
        ct = 0
    ct += 1
sums = [0, 0] + sums

ans = -1
lensums = len(sums)
for uragaesu in range(K, K + 1):  # 1
    for start in range(N):  # 1e5 / 2 ... TLE?
        if start + 2 * uragaesu + 1 >= lensums:
            break
        ans = max(ans, sums[start + 2 * uragaesu + 1] - sums[start])
    if ans == sums[-1]:
        break
        
print(ans if ans >= 0 else sums[-1])

Submission status: Wrong Answer

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

left_ac = [0]
right_ac = [0]

prev = ""
for i in range(N):
    s = S[i]
    if s == "L":
        if i - 1 >= 0:
            if S[i - 1] == "L":
                left_ac.append(left_ac[-1] + 1)
            else:
                left_ac.append(left_ac[-1])
        else:
            left_ac.append(left_ac[-1])
        right_ac.append(right_ac[-1])
    else:
        if i + 1 < N:
            if S[i + 1] == "R":
                right_ac.append(right_ac[-1] + 1)
            else:
                right_ac.append(right_ac[-1])
        else:
            right_ac.append(right_ac[-1])
        left_ac.append(left_ac[-1])
left_ac.pop(0)
right_ac.pop(0)
# print(left_ac)
# print(right_ac)

left = 0
right = 0
ans = right_ac[-1] + left_ac[-1]
remain = K
while left < N:
    s = S[left]
    while remain > 0 and right < N:
        if S[right] != s:
            if (right + 1 < N and S[right + 1] == s) or (right == N - 1 and S[N - 1] != s):
                remain -= 1
        right += 1

    if s == "L":
        #print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right < N - 1:
            tmp += right_ac[-1] - right_ac[right + 1]
            tmp += left_ac[-1] - left_ac[right + 1]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)
    else:
        #print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right < N - 1:
            tmp += right_ac[-1] - right_ac[right+1]
            tmp += left_ac[-1] - left_ac[right+1]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)

    if right == left:
        right += 1
    if left + 1 < N and S[left + 1] != s:
        remain += 1
    left += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=(int(i) for i in input().split())
S=input()

p=0
m=0
r=1
r_list=[]
bit=True
ans=0
if S[0]=="R":
    m+=1
if S[0]=="L":
    p+=1
for i in range(N-1):
    if S[i]=="R" and S[i+1]=="L":
        p+=1
        if bit==True:
            r+=1
    elif S[i]=="L" and S[i+1]=="R":
        m+=1
        if bit==True:
            r+=1
    else:
        r_list.append(r)
        bit=False
        r=0
        ans+=1
if S[N-1]=="R":
    m+=1
    if bit==True:
        r+=1
        r_list.append(r)
if S[N-1]=="L":
    p+=1
    if bit==True:
        r+=1
        r_list.append(r)
t=min(p,m)
ans+=min(t,K)*2

if p+m==2:
    if max(r_list)==p+m:
        if t<=K:
            ans-=1
if p+m==3:
    if max(r_list)==p+m:
        if t<=K:
            ans-=1
if p+m==4:
    if max(r_list)==p+m:
        ans-=1
    if max(r_list)==p+m-1:
        ans-=1

if ans>=N:
    ans=N-1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
h = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    h += 1
ans = h + 2 * K
if ans > N:
  ans = N - 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = input().split(" ")
N = int(N)
K = int(K)
s = input()
#a_sub = input().split(" ")
#a = [int(n0) for n0 in a_sub]
# print(a)

sc = 0
no = 0
"""
if s[0]=="R" and s[1]=="R":
    sc = sc+1
else:
    no = no+1

if s[N-2]=="L" and s[N-1]=="L":
    sc = sc+1
else:
    no = no+1
print(sc)
"""
for xi in range(0, N-1):
    if s[xi]==s[xi+1]:
        sc = sc +1
    else:
        no = no+1
# print(sc)
if no>K:
    sc = sc + 2*K
else:
    sc = sc + 2*(no-1)+no%2

print(sc)

Submission status: Wrong Answer

Solution code:
N, K = input().split(" ")
N = int(N)
K = int(K)
s = input()
#a_sub = input().split(" ")
#a = [int(n0) for n0 in a_sub]
# print(a)

sc = 0
no = 0
"""
if s[0]=="R" and s[1]=="R":
    sc = sc+1
else:
    no = no+1

if s[N-2]=="L" and s[N-1]=="L":
    sc = sc+1
else:
    no = no+1
print(sc)
"""
for xi in range(0, N-1):
    if s[xi]==s[xi+1]:
        sc = sc +1
    else:
        no = no+1
print(sc)
if no>K:
    sc = sc + 2*K
else:
    sc = sc + 2*(no-1)+no%2

print(sc)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
h = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    h += 1
ans = h + 2 * K
if ans == N:
  ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
"""考え方
ブロックとそのブロック内の人数を調べることで、「現時点での幸福度」を調べる。
一回変換するごとに幸福度が2向上する。

"""

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


before_s = 'a'
cnt_str_cng = 0
ans = 0
for s in S:
  if s == before_s:
    ans += 1
  else:
    cnt_str_cng += 1
  before_s = s

if cnt_str_cng - 1 <= K:
  ans = N-1
else:
  ans += K * 2

print(ans)

Submission status: Wrong Answer

Solution code:
import re

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

LL = re.finditer('L+', S)
RR = re.finditer('R+', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l.group(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.group(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: Wrong Answer

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

res = 0
pre = None
add = {2: 0}
add[1] = 0 if S[0] == S[-1] else 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[1] + add[2] >= K:
    print(N - 1)
elif 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: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = input()
ans = 0
spec = False
half = int(n / 2)
#print(s[half:n])
if (s[0:half].count("L") == half or s[0:half].count("R") == half) and k == 1 and n > 2:
    if s[half : n].count("L") == half or s[half:n].count("R") == half:
        spec = True

for i in range(n - 1):
    if s[i] == s[i + 1] :
        ans += 1
 
#print(ans)
if spec :
    if ans + 1 > n:
        print(n)
    else :
        print(ans + 1)
else :
    if ans + 2 * k > n:
        print(n)
    else :
        print(ans + 2 * k)

Submission status: Wrong Answer

Solution code:
N,K=(int(i) for i in input().split())
S=input()

p=0
m=0
r=1
r_list=[]
bit=True
ans=0
if S[0]=="R":
    m+=1
if S[0]=="L":
    p+=1
for i in range(N-1):
    if S[i]=="R" and S[i+1]=="L":
        p+=1
        if bit==True:
            r+=1
    elif S[i]=="L" and S[i+1]=="R":
        m+=1
        if bit==True:
            r+=1
    else:
        r_list.append(r)
        bit=False
        r=0
        ans+=1
if S[N-1]=="R":
    m+=1
    if bit==True:
        r+=1
        r_list.append(r)
if S[N-1]=="L":
    p+=1
    if bit==True:
        r+=1
        r_list.append(r)
t=min(p,m)
ans+=min(t,K)*2

if p+m==2:
    if t<=K:
        ans-=1
if p+m==3:
    if max(r_list)==p+m:
        if t<=K:
            ans-=1
if p+m==4:
    if max(r_list)==p+m:
        ans-=1
    if max(r_list)==p+m-1:
        ans-=1

if ans>=N:
    ans=N-1
print(ans)

Submission status: Wrong Answer

Solution code:
# run-length encoding, decoding
def rle_encode(data):
    encoding = ''
    prev_char = ''
    count = 1

    if not data: return ''

    for char in data:
        # If the prev and current characters
        # don't match...
        if char != prev_char:
            # ...then add the count and character
            # to our encoding
            if prev_char:
                encoding += str(count) + prev_char + ' '
            count = 1
            prev_char = char
        else:
            # Or increment our counter
            # if the characters do match
            count += 1
    else:
        # Finish off the encoding
        encoding += str(count) + prev_char + ' '
        return encoding

N, K = [int(s) for s in input().split()]
S = input()
S_rle = rle_encode(S).split()
total = 0
for i, bunch in enumerate(S_rle):
  total += int(list(bunch)[0]) - 1

if len(S_rle) > 2*K:
  print(total+2*K)
elif len(S_rle) >= 2*K:
  print(total+2*K-1)
else:
  print(N-1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
S=input()+'X'
if n==1:
  print(0)
  exit()
if n==2:
  print(1)
  exit()
A=[0]
l=0
r=0
for i in range(n):
  if S[i]=='L':
    l+=1
    if S[i+1]!='L':
      A.append(l)
      l=0
  if S[i]=='R':
    r-=1
    if S[i+1]!='R':
      A.append(r)
      r=0
A=sorted(A)
z=A.index(0)
L=sum(A[z+1:])-len(A[z+1:])-sum(A[:min(z,k)])+min(z,k)
R=sum(A[:z])+len(A[:z])-sum(A[-min(n-z,k):])-min(z,k)
if len(A[z+1:])==min(z,k):
  L-=1
if len(A[:z])==min(z,k):
  R+=1
print(max(L,-R))

Submission status: Wrong Answer

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 n == 1:
    i = 0
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:
    l = len(b)
    if l % 2 == 0:
        l += 1
    ans1 += (2*k - l)
ans1 = min(n-1, ans1)
for i in range(min(2*k, len(a))):
    ans2 += a[i]
if len(a) <= 2*k:
    l = len(a)
    if l % 2 == 0:
        l += 1
    ans2 += (2*k - l)
ans2 = min(n-1, ans2)
print(max(ans1, ans2))

Submission status: Wrong Answer

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

left_ac = [0]
right_ac = [0]

prev = ""
for i in range(N):
    s = S[i]
    if s == "L":
        if i - 1 >= 0:
            if S[i - 1] == "L":
                left_ac.append(left_ac[-1] + 1)
            else:
                left_ac.append(left_ac[-1])
        else:
            left_ac.append(left_ac[-1])
        right_ac.append(right_ac[-1])
    else:
        if i + 1 < N:
            if S[i + 1] == "R":
                right_ac.append(right_ac[-1] + 1)
            else:
                right_ac.append(right_ac[-1])
        else:
            right_ac.append(right_ac[-1])
        left_ac.append(left_ac[-1])
left_ac.pop(0)
right_ac.pop(0)
# print(left_ac)
# print(right_ac)

left = 0
right = 0
ans = right_ac[-1] + left_ac[-1]
remain = K
while left < N:
    s = S[left]
    while remain > 0 and right < N:
        if S[right] != s:
            if (right + 1 < N and S[right + 1] == s) or (right == N - 1 and S[N - 1] != s):
                remain -= 1
        right += 1

    if s == "L":
        #print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right < N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)
    else:
        #print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right < N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)

    if right == left:
        right += 1
    if left + 1 < N and S[left + 1] != s:
        remain += 1
    left += 1
print(ans)

Submission status: Wrong Answer

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 = ""
buf = []
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: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
Rs = []
now = S[0]
count = -1

for i in range(N):
    if S[i] == now:
        count += 1
    else:
        Rs.append(count)
        count = 0
        now = S[i]
Rs.append(count)
ans = 0
if K == 0:
  ans = sum(Rs)
else:
  if K >= len(Rs) - 2:
      ans = N-1
  elif K == len(Rs) - 3:
      ans = N-2
  else:
      ans = sum(Rs) + 2 * K

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = input()
ans = 0
spec = False
half = int(n / 2)
#print(s[half:n])
if (s[0:half].count("L") == half or s[0:half].count("R") == half) and k == 1 and n > 2:
    if s[half : n].count("L") == half or s[half:n].count("R") == half:
        spec = True

for i in range(n - 1):
    if s[i] == s[i + 1] :
        ans += 1
 
#print(ans)
if spec :
    print(ans + 1)
else :
    print(ans + 2 * k)

Submission status: Wrong Answer

Solution code:
# run-length encoding, decoding
def rle_encode(data):
    encoding = ''
    prev_char = ''
    count = 1

    if not data: return ''

    for char in data:
        # If the prev and current characters
        # don't match...
        if char != prev_char:
            # ...then add the count and character
            # to our encoding
            if prev_char:
                encoding += str(count) + prev_char + ' '
            count = 1
            prev_char = char
        else:
            # Or increment our counter
            # if the characters do match
            count += 1
    else:
        # Finish off the encoding
        encoding += str(count) + prev_char + ' '
        return encoding

N, K = [int(s) for s in input().split()]
S = input()
S_rle = rle_encode(S).split()
total = 0
for i, bunch in enumerate(S_rle):
  total += int(list(bunch)[0]) - 1

if len(S_rle) > 2*K:
  print(total+2*K)
elif len(S_rle) >= 2*K-1:
  print(total+2*K-1)
else:
  print(N-1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
Slist = []
for k in range(N):
    Slist.append(S[k])
#LR数できまる.
#一番外はRとLをそれぞれ付けて考える
#Lの次にRならLに変えてRが続くならそれもLに返る
ans = 0
count = 0
for i in range(N-1):
    if count == K:
        break
    if Slist[i] == "L" and Slist[i+1] == "R":
        count += 1
        for p in range(i+1,N):
            if Slist[p] == "R":
                Slist[p] = "L"
            else:
                break

for j in range(N-1):
    if Slist[j] == Slist[j+1]:
        ans += 1

print(ans)

#print(Slist)

Submission status: Wrong Answer

Solution code:
import copy
n,K= map(int,input().split())
S = list(input())
ans = 0
flag = 0
num = 0
while num < K:
  for i in range(2,n-1):
    if num == K:
      break
    for j in range(1,n-i):
      if num == K:
        break
      if S[j] != S[j+i] and S[j-1] != S[j+i-1] and S[j] == S[j+i-1]:
        for k in range(i//2):

          tmp = copy.deepcopy(S[j+k])
          if S[j+i-1-k] == "L":
            S[j+k] ="R"
          else:
            S[j+k] ="L"
          if tmp == "L":
            S[j+i-1-k] ="R"
          else:
            S[j+i-1-k] ="L"
  
        num += 1
    
  if num == K :
    break
  a = S.count("L")
  if K-num > abs(n - 2*a):
    ans +=  K-num
    break
  else:
    ans += abs(n-2*a)
    break
        
    
for i in range(n-1):
  if S[i] == S[i+1]:
    ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
n_k_str = input()
n_k_list = n_k_str.split(" ")
N = int(n_k_list[0])
K = int(n_k_list[1])
S = list(input())

pre_s = S.pop(0)
pre_index = -1
result = 0
for i,s in enumerate(S):
    if s != pre_s:
        temp = i - pre_index - 1
        print(temp)
        result += temp
        pre_index = i
    pre_s = s

temp = len(S) - pre_index - 1
result += temp

result += K*2
if result >= N:
    result = N - 1

print(result)

Submission status: Wrong Answer

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)


old = S[0]
border = 0
for i in range(1, N):
    if old != S[i]:
        border += 1
        old = S[i]
#print(border)

changed = 2 * K
if changed < border:
    print(happy_num + 2 * K)
else:
    if border % 2 == 0:
        print(N - 1)
    else:
        print(happy_num + 1 + 2 * (K - 1))

Submission status: Wrong Answer

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

res = 0
pre = None
r_s = {1: 0, 2: 0}
l_s = {1: 0, 2: 0}


for s in S:
    if pre is None:
        if s == "L":
            l_s[1] = 1
    elif pre == s:
        res += 1
    elif pre == "R":
        r_s[2] += 1
        l_s[2] += 1
    pre = s

if pre == "R":
    r_s[1] = 1


def calc(s, K):
    c = 0
    m = min(K, s[2])
    c += 2 * m
    K -= m
    if K > 0:
        c += s[1]
    return c


r_c = calc(r_s, K)
l_c = calc(l_s, K)

print(res + max(r_c, l_c))

Submission status: Wrong Answer

Solution code:
import sys
import copy

input = sys.stdin.readline

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

for n in range(K):
	pre = 'none'
	LR = False
	RL = False
	l,r = -1,-1
	for i in range(N-1):
		if S[i]=='L' and S[i+1]=='R':
			LR = True
			l = i+1
			break
		elif S[i]=='R' and S[i+1]=='L':
			RL = True
			l = i+1
			break

	if LR==True:
		for i in range(l+1,N-1):
			if S[i]=='R' and S[i+1]=='L':
				r = i
				break
		if r==-1:
			r = N-1
	elif RL==True:
		for i in range(l+1,N-1):
			if S[i]=='L' and S[i+1]=='R':
				r = i
				break
		if r==-1:
			r = N-1
	else:
		break

	temp = copy.deepcopy(S[l:r+1])
	for i in range(len(temp)):
		if temp[i]=='L':
			temp[i]='R'
		else:
			temp[i]='L'

	for ii in range(l,r+1):
		S[ii] = temp[ii-l]

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s="#"+input()+"#"
ans=0
for i in range(1,n+1):
    if s[i]=="R" and s[i+1]=="R":
        ans+=1
    if s[i]=="L" and s[i-1]=="L":
        ans+=1
a=s.count("LR")+s.count("RL")
if k>=a:
    ans=n-1
else:
    ans+=2*k
print(ans)

Submission status: Wrong Answer

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

ans = K
streak = 1

for i in range(N-1):
    if S[i] == S[i+1]:
        streak += 1
    else:
        if streak > 1:
            ans += streak
            streak = 1

if streak > 1:
    ans += streak

if S.startswith("LL"):
    ans -= 1
if S.endswith("RR"):
    ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = [int(x) for x in input().split()]
S = list(input())
point = N - 1
count = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        point -= 1
        count += 1
if K >= count:
    print(N-1)
else:
    print(point+2*K)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

lr = 0
rl = 0
cnt = 0
for i in range(N):
    if i >= 1:
        if S[i] == S[i - 1] == 'L':
            cnt += 1
        if S[i] == 'R' and S[i - 1] == 'L':
            lr += 1
        if S[i] == 'L' and S[i - 1] == 'R':
            rl += 1
    if i <= N - 2:
        if S[i] == S[i + 1] == 'R':
            cnt += 1

op = min(lr, rl, K)
print(cnt + op * 2 + K - op)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
ans = 0
cnt = 0
s = list(input())
for i in range(N-1):
    if s[i] == s[i+1]:
        ans += 1
    else:
        cnt += 1
if cnt == 1:
    ans = ans + 1
else:
    ans = ans + 2 * min(K,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, K = map(int, input().split())
S = ["a"] + list(input()) + ["a"]

shiawase = 0
# 幸せカウント
for i in range(1, N+1):
    if S[i] == "L":
        if S[i-1] == "L":
            shiawase += 1
    else:
        if S[i+1] == "R":
            shiawase += 1

if N == 2:
    print(shiawase)
    sys.exit(0)

if N == 3:
    if K > 0:
        print(2)
    else:
        print(shiawase)
    sys.exit(0)

# N >= 4
S = S[1:-1]
# if S[0] == "L":
#     S = ["R"] + S
# else:
#     S = ["L"] + S
# if S[-1] == "L":
#     S.append("R")
# else:
#     S.append("L")

left = 0
right = N-1

# for i in range(K + 2):
while K > 0:
    # left, right をすすめる
    while left < N-1 and S[left] == S[left+1]:
        left += 1
    while right > 0 and S[right] == S[right-1]:
        right -= 1

    if left >= right - 1:
        break

    shiawase += 2

    # if left == 0:
    #     shiawase -= 1
    # if right == N-1:
    #     shiawase -= 1

    K -= 1

lcount = S.count("L")
rcount = S.count("R")


shiawase += min(K, lcount, rcount)


print(shiawase)