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

L = []
R = []
cnt = 1
for i in range(N):
    if i == 0:
        continue
    if S[i-1] == S[i]:
        cnt += 1
        if i == N-1:
            if S[i] == "L":
                L.append([i-cnt+1,cnt])
            else:
                R.append([i-cnt+1,cnt])
    else:
        if S[i] == "L":
            R.append([i-cnt,cnt])
        else:
            L.append([i-cnt,cnt])
        if i == N-1:
            if S[i] == "L":
                L.append([N-1,1])
            else:
                R.append([N-1,1])
        cnt = 1
R.sort(key=lambda x:x[1])
L.sort(key=lambda x:x[1])

#Rを最大化
ans = 0
res = 0
c = 0
s = S
while c < K:
    if L:
        ind,x = L.pop()
        c += 1
        s = s[:ind]+"R"*x+s[ind+x:]
    else:
        break
#評価
for i in range(N):
    if s[i] == "L":
        if i == 0:
            continue
        if s[i-1] == "L":
            res += 1
    if s[i] == "R":
        if i == N-1:
            continue
        if s[i+1] == "R":
            res += 1
if ans < res:
    ans = res
#Lを最大化
res = 0
c = 0
s = S
while c < K:
    if R:
        ind,x = R.pop()
        c += 1
        s = s[:ind]+"L"*x+s[ind+x:]
    else:
        break
#評価
for i in range(N):
    if s[i] == "L":
        if i == 0:
            continue
        if s[i-1] == "L":
            res += 1
    if s[i] == "R":
        if i == N-1:
            continue
        if s[i+1] == "R":
            res += 1
if ans < res:
    ans = res
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    s = list(input())
    if n == 1:
        print(0)
        exit()
    elif n == 2:
        print(1)
        exit()

    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)
    r = sorted(r, reverse=True)

    import copy
    ss = copy.deepcopy(s)
    for i in range(min(k,len(l))):
        for j in range(l[i][0]):
            ss[l[i][1] + j] = "R"
    if k >= len(l) or k >= len(r):
        print(n - 1)
        exit()
    ansa = 0
    for i in range(n-1):
        if ss[i] == ss[i + 1]:
            ansa += 1


    for i in range(min(k,len(r))):
        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]:
            ansb += 1
    print(max(ansa, ansb))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
#LR数できまる.
#両側が同じときはさらにもう一つ減る
LR = 0

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

if LR > K:
    ans = N - (LR-K)*2
else:
    ans = N

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

RL = 0

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

if RL > K:
    ans2 = N - (RL-K)*2
else:
    ans2 = N

if S[0] == S[-1]:
    ans2 -= 1

if ans2 > ans:
    print(ans2)
else:
    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+2:
  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 = list(map(int, input().split()))
S = list(input())

cnt = 0
score = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        cnt += 1
    else:
        score += 1

if K < cnt:
  score += 2*K
else:
  score += 2*cnt

print(score+1)

Submission status: Wrong Answer

Solution code:
def count_happiness(S):
    happiness = 0
    for n in range(N):
        if(S[n] == "L" and n > 0 and S[n] == S[n-1]):
            happiness += 1
        elif(S[n] == "R" and n < N -1 and S[n] == S[n+1]):
            happiness += 1
    return happiness

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

LR_RL_unhappy_pair = 0
LR_unhappy = 0
RL_unhappy = 0
for n in range(N-1):
    if(S[n] == "R" and S[n+1] == "L"):
        RL_unhappy += 1
    if(S[n] == "L" and S[n+1] == "R"):
        LR_unhappy += 1

change_pair_count  = min(K, min(RL_unhappy, LR_unhappy))
change_single_count = 0
if(K > change_pair_count):
    remain = K - change_pair_count
    changable = abs(RL_unhappy  - LR_unhappy)
    change_single_count = min(RL_unhappy, changable) 
print(count_happiness(S) + 2 * change_pair_count + change_single_count)

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+2:
  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()


def split(s):
    last = ''
    new = []
    for x in s:
        if last != x:
            new.append(x)
        else:
            new[-1] += x
        last = x
    return new


def transform(s, k):

    for _ in range(k):
        s = split(s)
        if len(s) == 1:
            break
        ls = list(map(len, s))
        idx = ls.index(min(ls))
        if idx == 0:
            idx = ls[1:].index(min(ls[1:]))+1

        # print(s, idx, ls)
        s[idx] = s[idx].replace('L', 'X').replace('R', 'L').replace('X', 'R')
        s = ''.join(s)
    # print(s)
    return s


s = transform(s, k)


def count(s):
    cnt = 0
    for i in range(len(s)):
        if i+1 < len(s) and s[i] == 'R' and s[i+1] == 'R':
            cnt += 1
        elif i-1 >= 0 and s[i] == 'L' and s[i-1] == 'L':
            cnt += 1
    return cnt


print(count(s))

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(len(A)-z-1,k)
R=sum(A[:z])+len(A[:z])-sum(A[-min(z,k):])-min(z,k)
print(max(L,-R))

Submission status: Wrong Answer

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

ranlength_l = []
count = 1
for i in range(1,len(S)):
    if(S[i] != S[i-1]):
        ranlength_l.append([S[i-1],count])
        count = 1
    else:
        count += 1
    if(i==len(S)-1):
        ranlength_l.append([S[len(S)-1],count])

target = S[0]
if(target=="L"):
    changed = "R"
else:
    changed = "L"

ans = N-len(ranlength_l)
for const in (ranlength_l[1:len(ranlength_l)-1][::2]):
    if(K==0):
        break
    ans += 2
    K = K-1

if(K!=0 and len(ranlength_l)!=1):
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
SC=[]
c=1
for i in range(N-1):
    if S[i]!=S[i+1]:
        SC.append(c)
        c=1
    else:
        c+=1

if c!=1:
    SC.append(c)

L=len(SC)

if L<=K+1:
    print(N-1)

else:
    ans=sum(SC[0:2*K+1])-1
    for i in range(2*K+1,L):
        if SC[i]>1:
            ans+=SC[i]-1
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
s_ = np.array([1]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1

l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    if n % 2 == 0:
        a_l = s_[0]
        a_r = s_[-1]
        for i in range(1,n//2):
            if s_[i] == a_l:
                ans += 1
            else:
                a_l = s_[i]
            if s_[-(i+1)] == a_r:
                ans += 1
            else:
                a_r = s_[-(i+1)]
        if a_r == a_l:
            ans += 1
    else:
        a_l = s_[0]
        a_r = s_[-1]
        for i in range(1,n//2):
            if s_[i] == a_l:
                ans += 1
            else:
                a_l = s_[i]
            if s_[-(i+1)] == a_r:
                ans += 1
            else:
                a_r = s_[-(i+1)]
        if a_l == s_[n // 2 + 1] or a_r == s_[n // 2 + 1]:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
A,B = list(map(int,input().split()))
a =input()
ans=0
an=0
if A==1:
  print(0)
else:
  for i in range (A-1):
    if a[i]==a[i+1]:
      ans +=1
    else :
      an +=1
  if an <=B:
    ans+=an
  else :
    ans+=B*2
  print(ans)

Submission status: Wrong Answer

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

happiness = 0
cnt = 0
if N == 1:
    print(0)
elif N == 2:
    print(1)
else:
    if S[2] == S[1]:
        happiness += 1
    if S[1] == S[0]:
        happiness += 1
    for i in range(2,N):
        if cnt < K and S[i] == S[i-2] and S[i] != S[i-1]:
            happiness += 2
            S[i-1] = S[i]
            cnt += 1
        elif S[i] == S[i-1]:
            happiness += 1
    if cnt < K:
        happiness += 1
    print(happiness)

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 (2*k - l) % 2 == 1:
        ans1 += (2*k - l)
    else:
        ans1 += (2*k - l) + 1
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 (2*k - l) % 2 == 1:
        ans2 += (2*k - l)
    else:
        ans2 += (2*k - l) + 1
ans2 = min(n-1, ans2)
ans = max(ans1, ans2)
if ans1 != ans2:
    ans = min(ans1, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = input()
ans = 0
count = 0
if n == 1:
  print(0)
else:
  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
      if 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: 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(len(A)-z-1,k)
R=sum(A[:z])+len(A[:z])-sum(A[-min(z,k):])-min(z,k)
if len(A[z+1:])==min(len(A)-z-1,k):
  L-=1
if len(A[:z])==min(z,k):
  R+=1
print(max(L,-R))

Submission status: Wrong Answer

Solution code:
#import numpy as np

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

done = 0


out = 0

#gid_list = []
#gnum_list = []
#gkukan_list = []
#
#cur_gid = 0
#cur_gnum = 0
#cur_gstart = 0

for i in range(N):
    cur_c = s[i]
    
    if s[i] == "L" and i >= 1 and s[i-1] == "L":
        out += 1
    elif s[i] == "R" and i <= N-2 and s[i+1] == "R":
        out += 1

#    if i >= 1:
#        if cur_c != before_c:
#            cur_gend =i-1
#            cur_gkukan = [cur_gstart, cur_gend]
#            gkukan_list.append(cur_gkukan)
#            cur_gstart = i
#
#            gnum_list.append(cur_gnum)
#            cur_gnum = 0
#
#            cur_gid += 1
#    
#    cur_gnum += 1
#    gid_list.append(cur_gid)
#
#    before_c = cur_c
#
#cur_gend =N-1
#cur_gkukan = [cur_gstart, cur_gend]
#gkukan_list.append(cur_gkukan)
#gnum_list.append(cur_gnum)
#len_g = len(gnum_list)



#for i in range(N):
#    if done < K:
#        if 1 <= i <= N-2:
#            # L(RL) -> LLL
#            if s[i-1] == "L" and s[i] == "R" and s[i+1] == "L":
#                s[i] = "L"
#                out += 2
#                done += 1
#    else:
#        break

#print("current", out, done, s)
i = 0
while i < N:
    if done < K:
        if 0 <= i <= N-2:
           # L(RL) -> LLL
            if s[i] == "L" and s[i+1] == "R":
                start_i = i+1
                i += 1

                found = True
                while s[i] == "R":
                    i += 1
                    if i >= N:
                        found = False
                        break
               
                # s[i] == "L" made

                if found:
                    end_i = i-1
                else:
                    end_i = N-1
                
                for j in range(start_i, end_i+1):
                    s[j] = "L"

                #print("found", found, start_i, end_i)
                if found:
                    out += 2
                else:
                    out += 1
                    break

                done += 1

                i -= 1 # s[i] == "R" ni modosu
        else:
            pass
            #print("false", i)

        i += 1
    else:
        break


for i in range(N):
    if done < K:
        if 1 <= i <= N-2:
            # R(LR) -> RRR
            if s[i-1] == "R" and s[i] == "L" and s[i+1] == "R":
                s[i] = "R"
                out += 2
                done += 1
    else:
        break

for i in range(N-1):
    if done < K:
        if s[i] == "R" and s[i+1] == "L":
            s[i] = "L"
            out += 1
            done += 1
    else:
        break



i = 0
if done < K:
    if s[0] == "R":
        start_i = 0
        i += 1

        found = True
        while s[i] == "R":
            i += 1
            if i >= N:
                found = False
                break

        if found:
            end_i = i-1
            for j in range(start_i, end_i+1):
                s[j] = "L"
            out += 1
            #print("test0")
            
        done += 1


print(out)

Submission status: Wrong Answer

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

cnt = 0
score = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        cnt += 1
    else:
        score += 1

if K < cnt:
  score += 2*K
else:
  score += 2*cnt

print(score)

Submission status: Wrong Answer

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

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

aihan = []
ai = 1
han = -1
happi = 0
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        aihan.append(ai)
    elif S[i] == 'L' and S[i+1] == 'R':
        aihan.append(han)
    else:
        aihan.append(happi)

aihan_count = 0

for i, e in enumerate(aihan):
    if e * aihan_count < 0:
        happiness += 2
        K -= 1
    aihan_count += e
    if K <= 0:
        break

if K > 0:
    if S[0] == 'L':
        if aihan_count < 0:
            happiness += 1
            K -= 1
            aihan_count += 1
    if K > 0:
        if S[N-1] == 'R':
            if aihan_count < 0:
                happiness += 1
                K -= 1
                aihan_count += 1

print(happiness)

Submission status: Wrong Answer

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

score = 0
change = 0
for i in range(n-1):
  if string[i] == string[i+1]:
    score += 1
  else:
    change += 1

t = min(change, k)
score = score + 2*t
if score == n:
  score = score - 1
print(score)

Submission status: Wrong Answer

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]

        c = 2 * K + 1
        if len(b) <= c:
            print(sum(b) - 1)
            exit()

        ans = 0
        for i in range(len(b) - c):
            current = sum(b[:i]) + sum(b[i:c + i]) + sum(b[c + i:]) - (len(b) - c + 1)
            ans = max(ans, current)

        print(ans)


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

Submission status: Wrong Answer

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)
    r = sorted(r, reverse=True)

    import copy
    ss = copy.deepcopy(s)
    for i in range(min(k,len(l))):
        for j in range(l[i][0]):
            ss[l[i][1] + j] = "R"
    if k >= len(l) or k >= len(r):
        print(n - 1)
        exit()
    ansa = 0
    for i in range(n-1):
        if ss[i] == ss[i + 1]:
            ansa += 1


    for i in range(min(k,len(r))):
        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]:
            ansb += 1
    print(max(ansa, ansb))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
input = raw_input

def score(s):
    n = len(s)
    ans = 0
    for i in range(n):
        if s[i] == "L" and i >= 1 and s[i-1] == "L":
            ans += 1
        elif s[i] == "R" and i <= n-2 and s[i+1] =="R":
            ans += 1
    return ans

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

if S=="RL":
    print(0)
    exit()
if S=="LR":
    print(0)
    exit()
if S=="RLR" or S=="LRL":
    if K == 1:
        print(1)
        exit()
    else:
        print(2)
        exit()

s = score(S)
k = 0
lr = 0
rl = 0
for i in range(N-1):
    if S[i] == "L" and S[i+1] =="R":
        lr += 1
    if S[i] == "R" and S[i+1] =="L":
        rl += 1
lrl = 0
rlr = 0
for i in range(N-2):
    if S[i] == "L" and S[i+1] =="R" and S[i+2] =="L":
        lrl += 1
    if S[i] == "R" and S[i+1] =="L" and S[i+2] =="R":
        rlr += 1

if (lrl == 1 and rl == 1 and lr == 1) or (rlr == 1 and rl == 1 and lr == 1):
    if K >= 2:
        print(s+2)
        exit()
    elif K == 1:
        print(s+1)
        exit()
    else:
        print(s)
        exit()

#print(s)
#print(lr, rl)
c = min(K, lr, rl)
s += 2 * c
K -= min(lr, rl)
if lr >= rl:
    rl = 0
    lr -= rl
else:
    lr = 0
    rl -= rl
if K > 0:
    if S[0] == "L" and rl > 0:
        s += 1
        K -= 1
        rl -= 1
if K > 0:
    if S[-1] == "R" and lr > 0:
        s += 1
        K -= 1
        lr -= 1
print(s)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
S = list(map(str,input()))
s = 1
e = len(S)-2
flag = 0
k = 0
while s < e and k < K:
    if S[s-1] == 'L' and S[s] == 'R' and S[e] == 'R' and S[e+1] == 'L':
        S[s] = 'L'
        S[e] = 'L'
        k += 1
        s += 1
        e -= 1
    elif S[s-1] == 'R' and S[s] == 'L' and S[e] == 'L' and S[e+1] == 'R':
        S[s] = 'R'
        S[e] = 'R'
        k += 1
        s += 1
        e -= 1
    else:
        if flag:
            s += 1
            flag = 0
        else:
            e -= 1
            flag = 1
    
ans = 0
for i in range(1,len(S)):
    if S[i] == S[i-1]:
        ans += 1

if k < K:
    isl = 0
    isr = 0
    for i in range(N):
        if S[0] == 'L' and S[i] == 'R' and isl != 1 and k < K:
            ans += 1
            isl = 1
            k += 1
        if S[-1] == 'R' and S[i] == 'L' and isr != 1 and k < K:
            ans += 1
            isr = 1
            k += 1

print(ans)

Submission status: Wrong Answer

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

# 反転可能回数が人数より多ければ端の人以外全員幸福にできる
if K >= N:
    print(N - 1)
    exit()

# L=0,R=1として2進数に変換
S = int(input().replace('L', '0').replace('R', '1'), 2)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
s_ = np.array([1]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1

l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    if n % 2 == 0:
        a_l = s_[0]
        a_r = s_[-1]
        for i in range(1,n//2):
            if s_[i] == a_l:
                ans += 1
            else:
                a_l = s_[i]
            if s_[-(i+1)] == a_r:
                ans += 1
            else:
                a_r = s_[-(i+1)]
    else:
        a_l = s_[0]
        a_r = s_[-1]
        for i in range(1,n//2):
            if s_[i] == a_l:
                ans += 1
            else:
                a_l = s_[i]
            if s_[-(i+1)] == a_r:
                ans += 1
            else:
                a_r = s_[-(i+1)]
        if a_l == s_[n // 2 + 1] or a_r == s_[n // 2 + 1]:
            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(len(A)-z-1,k)
R=sum(A[:z])+len(A[:z])-sum(A[-min(z,k):])-min(z,k)
if len(A[z+1:])==min(len(A)-z-1,k):
  L-=1
if len(A[:z])==min(z,k):
  R+=1
print(L,R)
print(max(L,-R))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
S = input()
now = S[0]
flag = True
ans = 0
z = 0
l = 0
for i in range(N):
    if now == S[i] and flag:
        l += 1
        continue
    elif now != S[i] and flag:
        flag = False
        now = S[i]
    elif now == S[i]:
        ans += 1
    else:
        z += 1
        now = S[i]
z -= 1
r = 0
now = S[N-1]
for i in reversed(range(N)):
    if now == S[i]:
        r += 1
    else:
        break
if K>=z:
    print(N-1)
elif K==z-1 and S[0]==S[N-1]:
    print(N-3)
elif K==z-1 and S[0]!=S[N-1]:
    print(N-2)
else:
    print(ans+K*2+r-1+l-1)

Submission status: Wrong Answer

Solution code:
N,K = [int(x) for x in  input().split()]
S = list(input())
ans = [0]
a = []
for i in range(N-1):
  if S[i]!=S[i+1]:
  	ans.append(i)
ans.append(N-1)
#print(ans)
a = []
for i in range(1,len(ans)):
  a.append(ans[i]-ans[i-1])
a[0] +=1
ans2 = sum(a)-len(a)
#print(a)
#print(ans2)
if len(a)!=1:
  ans2 = ans2 +(2*K if len(a)*(len(a)+1)//2>=K else len(a)*(len(a)+1)//2*2)
  print(ans2)
  exit()
print(ans2)

Submission status: Wrong Answer

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

counts = []
count = 0
lr = 0
rl = 0
for i in range(N - 1):#start
  z = S[i]
  if S[i] == S[i + 1]:
    count += 1
  elif (S[i] == "L") and (S[i+1] == "R"):
    lr += 1
  elif (S[i] == "R") and (S[i+1] == "L"):
    rl += 1
 
minlr = min(lr, rl)
maxlr = max(lr, rl) 
if (maxlr == 1) and (minlr == 0):
  count += 1
  print(count)
else:
  minK = min(K, minlr)
  count += 2 * minK
  print(count)

Submission status: Wrong Answer

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)
    r = sorted(r, reverse=True)

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


    for i in range(min(k,len(r))):
        for j in range(r[i][0]):
            s[r[i][1] + j] = "L"
    if k >= len(r):
        print(n - 1)
        exit()
    ansb = 0
    for i in range(n-1):
        if s[i] == s[i + 1]:
            ansb += 1
    print(max(ansa, ansb))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = list(input())
temp = S[0]
ind = 0
cs = [1]
for i in range(N - 1):
  if S[i] == S[i + 1]:
    cs[ind] += 1
  else:
    cs.append(1)
    ind += 1
    temp = S[i + 1]
#print(cs)
cscs = [cs[0]] + [0] * (len(cs))
for i in range(len(cs) - 1):
  cscs[i + 1] = cscs[i] + cs[i + 1]
cscs = [0] + cscs
css = [cs[0]] + [0] * (len(cs))
for i in range(len(cs) - 1):
  css[i + 1] = css[i] + cs[i + 1] - 1
css = [0] + css
#print(css)
#print(cscs)
res = 0
for i in range(len(cs) - 2 * M + 1):
  temp = css[-2] - css[i + 2 * M] + css[max(i - 1, 0)]
  #print(temp,css[-2],css[i + 2 * M],css[max(i - 1, 0)])
  res = max(res, cscs[i + 2 * M] - cscs[i] + temp)
  #print(res - 1, i, i + 2 * M)
if len(css) - 2 <= 2 * M + 1:
  print(N - 1)
else:
  print(res - 1)

Submission status: Wrong Answer

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

happiness = 0
cnt = 0
if N == 1:
    print(0)
elif N == 2:
    print(1)
else:
    if S[2] == S[1]:
        happiness += 1
    if S[1] == S[0]:
        happiness += 1
    for i in range(2,N-1):
        if cnt < K and S[i] == S[i-2] and S[i] != S[i-1]:
            happiness += 2
            S[i-1] = S[i]
            cnt += 1
        elif S[i] == S[i-1]:
            happiness += 1
    if cnt < K:
        happiness += 1
    print(happiness)

Submission status: Wrong Answer

Solution code:
import math

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

happiness = 0
unh = 0

for i in range(N-1):
    if S[i] == 'L' and S[i+1] == 'L':
        happiness +=1
    elif S[i] == 'R' and S[i+1] == 'R':
        happiness +=1
    else:
        unh +=1

if K <= math.ceil(unh//2):
    K = K
elif K > math.ceil(unh//2):
    K = math.ceil(unh//2)
    happiness = N-1

print(happiness + 2*K)

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[2] > K:
    res += 2 * K
    print(res)
else:
    res += 2 * add[2]
    K -= add[2]
    if add[1] == 1 and S[-1] == "L":
        res -= 1
    if K > 0:
        res += add[1]
    print(res)