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

if n == 1:
        print(0)
else:        
        t = []
        tt = 0
        ss = s[0]
        for i in range(1,n):
                if s[i] != ss:
                        t.append(i - tt)
                        tt = i
                        ss = s[i]
        t.append(n - tt)
        cnt = sum(t) - len(t) 

        if k <= len(t) - 2:
                cnt += 2 * k
        elif k == len(t) - 1:
                cnt += 2 * (len(t) - 2) + 1
        else:
                cnt += 2 * (len(t) - 2) + 2
        print(cnt)

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()
        if ind == N-1 and x == 1:
            continue
        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()
        if ind == 0 and x == 1:
            continue
        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:
n,k=map(int,input().split())
s=input()

RL_count=s.count("RL")
LR_count=s.count("LR")
term_count=0
if s[0]=="L":
    term_count+=1
if s[n-1]=="R":
    term_count+=1

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

if k>RL_count:
    ans+=2*RL_count
    if LR_count>=1:
        ans+=1
    if LR_count==2 and k>RL_count+1:
        ans+=1
else:
    ans+=2*k

print(ans)

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):
    change_single_count += max(0, K - change_pair_count) 
print(count_happiness(S) + 2 * change_pair_count + change_single_count)

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(N - 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:
import sys
#input=sys.stdin.readline
sys.setrecursionlimit(3000)


#L=-1  R=1
n,k=map(int,input().split())
s=input()
#print(s)
t=s[0]
c=[-1,1][s[0]=="R"]
d=[0]

for i in range(1,n):
    if t!=s[i]:
        d.append(c)
        c=0
    t=s[i]
    c+=[-1,1][s[i]=="R"]
d.append(c)
c=len(d)

#print(d)
p=[-1,-1]
for i in range(1,c-1):
    tmp=(abs(d[i-1])+abs(d[i])+abs(d[i+1]))
    if tmp>p[0]:
        p[0]=tmp
        p[1]=i
i=p[1]
for j in range(1,k+1):
    if i+j*2>=c: break
    d[i+j*2]*=-1
#print(d)
chk=0
ans=0
for i in d:
    if (i>0 and chk>0) or (i<0 and chk<0):
        chk+=i
    else:
        if chk!=0: ans+=abs(chk)-1
        chk=i

print(ans)

Submission status: Wrong Answer

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

# find the largest subsequence
packet = []
direction = [S[0]]
seq = 1
for i in range(1, N - 1):
    if S[i] == direction[-1]:
        seq += 1
    else:
        packet.append(seq)
        seq = 1
        direction.append(S[i])
if S[N - 1] == direction[-1]:
    seq += 1
    packet.append(seq)
else:
    packet.append(seq)
    seq = 1
    direction.append(S[N - 1])
    packet.append(seq)

#print(packet)


start_color = S[0]
packet_len = len(packet)
for _ in range(K):
    if packet_len == 1:
        print(packet_len - 1)
        exit()

    max_sum = packet[0] + packet[1]
    max_idx = 0
    for i in range(1, packet_len - 1):
        if max_sum < packet[i - 1] + packet[i] + packet[i + 1]:
            max_sum = packet[i - 1] + packet[i] + packet[i + 1]
            max_idx = i
    if max_sum < packet[packet_len - 2] + packet[packet_len - 1]:
        max_idx = packet_len - 1

    #print(max_idx)

    if max_idx == 0:
        val = packet[0] + packet[1]
        packet = [val] + packet[2:]
        packet_len -= 1
        if start_color == 'L':
            start_color = 'R'
        else:
            start_color = 'L'
    elif max_idx == packet_len - 1:
        val = packet[-1] + packet[-2]
        packet = packet[:packet_len - 2] + [val]
        packet_len -= 1
    else:
        val = packet[max_idx - 1] + packet[max_idx] + packet[max_idx + 1]
        packet = packet[:max_idx - 1] + [val] + packet[max_idx + 2:]
        packet_len -= 2

    #print(packet)

ans = 0
for v in packet:
    ans += v - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

left, right = [], []
current = 0
l_happy, r_happy = 0, 0
for i, (s0, s1) in enumerate(zip(s, s[1:]), 1):
    if s0 != s1:
        dst, len_ = s0, i - current
        current = i
        if dst == 'L':
            heapq.heappush(left, -len_)
            l_happy += len_ - 1
        else:
            heapq.heappush(right, -len_)
            r_happy += len_ - 1
if s[-1] == 'L':
    heapq.heappush(left, -(len(s) - current))
    l_happy += (len(s) - current) - 1
else:
    heapq.heappush(right, -(len(s) - current))
    r_happy += (len(s) - current) - 1

if l_happy > r_happy:
    for _ in range(k):
        if right:
            len_ = -1 * heapq.heappop(right)
            l_happy += len_ + 1
    print(min(l_happy, n - 1))
else:
    for _ in range(k):
        if left:
            len_ = -1 * heapq.heappop(left)
            r_happy += len_ + 1
    print(min(r_happy, n - 1))

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*2
  else :
    ans+=B*2
  print(ans)

Submission status: Wrong Answer

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

if n == 1:
        print(0)
else:        
        t = []
        tt = 0
        ss = s[0]
        for i in range(1,n):
                if s[i] != ss:
                        t.append(i - tt)
                        tt = i
                        ss = s[i]
        t.append(n - tt)
        print(t)
        cnt = sum(t) - len(t) 

        if k <= len(t) - 2:
                cnt += 2 * k
        elif k == len(t) - 1:
                cnt += 2 * (len(t) - 2) + 1
        else:
                cnt += 2 * (len(t) - 2) + 2
        print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

k = []
a = 1
ans = 0
for i in range(1,N):
    if S[i] != S[i-1]:
        k.append(a)
        a = 1
    else :
        a += 1
        ans += 1
k.append(a)
size = len(k)
dp = [[0 for i in range(K+1)] for j in range(size)]
if k[0] == 1 :
    dp[0][0] = k[0]
else :
    dp[0][0] = k[0] - 1
for i in range(size-1):
    for j in range(K):
        if i != size-2:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+k[i]+1)
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]+k[i]-1)
        else :
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + k[i])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + k[i]-1)

print(max(dp[size-1]))

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):
    ans+=1

print(ans)

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(0,n-3):
    if num == K:
      break
    for j in range(i+3,n):
      if num == K:
        break
      if S[i] == S[j] and S[i+1] == S[j-1] and S[i] != S[i+1]:
        for k in range((j-i-1)//2+(j-i-1)%2):
          tmp = copy.deepcopy(S[i+1+k])
          if S[j-1-k] == "L":
            S[i+1+k] ="R"
          else:
            S[i+1+k] ="L"
          if tmp == "L":
            S[j-1-k] ="R"
          else:
            S[j-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:
import re
n, k = [int(i) for i in input().split()]
s = input()
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
a = 0
for i in range(k):
    left = s.find("LR")
    right = s.rfind("RL")
    if left == -1 or right == -1:
        a += 1
        break
    else:
        a += 2
    s = s[left : right]
b = 0
for i in range(k):
    left = s.find("RL")
    right = s.rfind("LR")
    if left == -1 or right == -1:
        b += 1
        break
    else:
        b += 2
    s = s[left : right]
cnt += max(a, b)
print(cnt)

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
cnt = same_cnt + rev_cnt * 2 + extra


if up_L_flg and up_R_flg and cnt != N-1:
    cnt += 1
elif up_L_flg and remain_cnt and cnt != N-1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
L = [int(i) for i in input().split()]
S = input()
N = L[0]
K = L[1]
count = 0

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

count += K * 2
if count > N:
    print(N)
elif count < N:
    print(count)
elif count == N:
    print(N-1)

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

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

#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=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(len(A)-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:
N,K = map(int, input().split())
S = input()

def eval(line):
    prev = 0
    happiness = 0
    for d in line:
        if prev == d:
            happiness += 1

#        print((d,prev))
        prev = d
    return happiness

orig_score = eval(S)
mikomi = (N - orig_score) // 2
if mikomi <= K:
    score = orig_score + mikomi*2
else:
    score = orig_score + K*2

print(score)

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:
  print(total+2*K-1)
else:
  print(N-1)

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+2, N):
            if S[j] == start:
                i = j
                k += 1
                output += 2
                if k == K:
                    return output
                break
            if j == N-1:
                return N - 1

    return output


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

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(len(A)-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:
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"
    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()
A=[]
tmp=1
for i in range(1,N):
    if S[i-1]==S[i]:
        tmp+=1
    else:
        A.append(tmp)
        tmp=1
A.append(tmp)

while K>0:
    #print(A)
    K-=1
    tmpmax=0
    tmpindex=0
    if len(A)>2:
        for i in range(1,len(A)-1):
            tmp=A[i-1]+A[i]+A[i+1]
            if tmp>tmpmax:
                tmpindex=i
                tmpmax=tmp
        A[tmpindex]=tmpmax
        A.pop(tmpindex-1)
        A.pop(tmpindex)
    else:
        break
        
if len(A)>=2:
    print(sum(A)-len(A))
else:
    print(N-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]
            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
N, K = map(int, input().split())
S = input()
tmp = S[0]
ans = 0
L = []
for i in range(K):
    cnt = 0
    for j in range(1, N):
        if tmp == S[j]:
            cnt += 1
            tmp = S[j]
        else:
            L.append(cnt)
            tmp = S[j]
            break
L.sort(reverse=True)
Ls = S.count("L")
Rs = N - Ls
print(max(Ls, Rs) + sum(L[:K]))

Submission status: Wrong Answer

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

if n==1:
  print(0)
  exit()

count=0
for i in range(1,n//2+1):
  if count==k:
    break
  if s[i-1]==s[i+1] and s[i]!=s[i-1]:
    s[i]=s[i-1]
    count+=1

  if count==k:
    break
  if s[n-i]==s[n-i-2] and s[n-i-1]!=s[n-i]:
    s[n-i-1]=s[n-i]
    count+=1

result=0
if count!=k:
  for i in range(1,n):
    if s[i-1]!=s[i]:
      result+=1
      li=s[:i+1]
      li.reverse
      for j in range(len(li)):
        if li[j]=='R':
          li[j]='L'
        else:
          li[j]='R'
      s[:i+1]=li[:i+1]    
    if count==k:
      break
    
if s[0]=='R' and s[1]=='R':
  result+=1
if s[-1]=='L' and s[-2]=='L':
  result+=1
for i in range(1,n-1):
  if (s[i]=='R' and s[i+1]=='R') or (s[i]=='L' and s[i-1]=='L'):
    result+=1
print(result)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin.readline
na = lambda: map(int, stdin().split())
ns = lambda: stdin().rstrip()
ni = lambda: int(ns())
def main():
  n, k = na()
  s = ns()+"0"

  ans = 0
  LRcnt = []
  cnt = 1
  for i in range(n):
    if s[i] == s[i+1]:
      ans += 1
      cnt += 1
    else:
      LRcnt.append(cnt)
      cnt = 1

  N = len(LRcnt)
  wa = [0] * (N+1)
  for i in range(N):
    wa[i+1] = wa[i] + LRcnt[i]

  ans = 0
  for i in range(N-k-2):
    ans = max(ans, wa[i+k+2] - wa[i] - 1 + sum(LRcnt[i+k+2:]) - len(LRcnt[i+k+2:]) + sum(LRcnt[:i+k+1]) - len(LRcnt[:i+k+1]))
  if ans == 0:
    print(sum(LRcnt)-1)
  else:
    if n % 2 == 1 and k % 2 == 1:
      ans += 1
    elif n % 2 == 1 and k % 2 == 0:
      ans -= 1
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
temp = raw_input().split()
S = raw_input()

N = int(temp[0])
K = int(temp[1])

ini_score = 0
ex_count = 0


S = list(S)

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

num_double_interface = 0
for i in range(1,N-1):
    if (S[i] != S[i-1]) and (S[i]!= S[i+1]):
#        print i, "double"                                                                                                                              
        if S[i] == "L":
            S[i] = "R"
        else:
            S[i] = "L"
        num_double_interface = num_double_interface + 1
        ex_count = ex_count + 1

    if ex_count==K:
        print ini_score + 2*num_double_interface
        exit()



current_score = ini_score + 2*num_double_interface
max_score = N-1

best_score = ini_score + 2*num_double_interface + (K-ex_count)

if best_score < max_score:
    print best_score
else:
    print max_score

Submission status: Wrong Answer

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

d = []
p = 0
for i in range(1,n):
    if s[i] == s[i-1]:
        p += 1
        
    else:
        d.append(p)
        p = 0
if p != 0:
    d.append(p)
res = sum(d)

n = len(d)

for i in range(k):
    if n >= 3:
        res += 2
        n -= 1
    elif n == 2:
        res += 1
        n -= 1
    else:
        break
print(res)

Submission status: Wrong Answer

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

counts = []

cnt = 1
for i in range(len(S)-1):
  if (S[i] == S[i+1]):
    cnt += 1
  else:
    if (cnt > 1):
      counts.append(cnt)
    cnt = 1
  if (i == len(S)-2 and cnt > 1):
    counts.append(cnt)
counts.sort(reverse=True)
print(sum(counts[0:K]) + K)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
S = input()

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

cur = S[0]
A = []
st = 0
tmp = is_ok[0]
for i in range(1, N):
    if S[i] == cur:
        tmp += is_ok[i]
    else:
        A.append((tmp, st, i, cur))
        st = i
        tmp = is_ok[i]
        cur = S[i]
A.append((tmp, st, N, cur))

LR = {'L': [], 'R': []}
for i in range(len(A)):
    cnt, st, end, d = A[i]
    if st == 0 or end == N:
        LR[d].append(1)
    else:
        LR[d].append(2)

LR['L'].sort(reverse=True)
LR['R'].sort(reverse=True)
ans = sum(is_ok)
ans += max(sum(LR['L'][:K]), sum(LR['R'][:K]))

print(ans)

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

i = 0
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 += 2
        #print("test0")
        
    done += 1

#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

print(out)