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: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
s = ns()

lr = 0
rl = 0
same = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        same += 1
    elif s[i] == "L":
        lr += 1
    else:
        rl += 1
dv = min(lr, rl, k)
ans = 0
ans += 2*dv
k -= dv
if s[0] == "L" and lr-dv > 0 and k > 0:
    ans += 1
    k -= 1
    lr -= 1
if s[0] == "R" and rl-dv > 0 and k > 0:
    ans += 1
    k -= 1
    rl -= 1
if s[-1] == "L" and rl-dv > 0 and k > 0:
    ans += 1
    k -= 1
    rl -= 1
if s[-1] == "R" and lr-dv > 0 and k > 0:
    ans += 1
    k -= 1
    lr -= 1

print(same + ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
ans = 0
pc = "_"
for c in S:
    if pc==c:
        ans += 1
    pc = c
k = N-1-ans
ans += min(K*2, k)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    s = S()
    r = 0
    a = 0
    t = '-'
    for c in s:
        if c == t:
            r += 1
        else:
            a += 1
        t = c
    kk = k * 2
    if a > kk:
        r += kk
    else:
        r += a - 1

    return r


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

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

cnt -= K * 2
cnt = max(cnt, 0)
print N - 1 - cnt

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
ans = 0
S = input()
for i in range(1,N):
    if S[i] == S[i-1]:
        ans += 1

print(min(ans+K*2,N-1))

Submission status: Accepted

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

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

ANS=N-1

for i in range(1,N):
    if S[i]!=S[i-1]:
        ANS-=1

print(min(N-1,ANS+2*K))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
group = 1
for c, d in zip(s, s[1:]):
    if c != d:
        group += 1
print(min(n - 1, n - (group - 2 * k)))

Submission status: Runtime Error

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

s_list=[]
for i in s:
    if i=="L":s_list.append(0)
    else:s_list.append(1)
start_num=s_list[0]
i=0
while k>0:
    if s_list[i]!=start_num:
        k-=1
        while i<n and s_list[i]!=start_num:
            s_list[i]=start_num
            i+=1
    i+=1
ans=0
for i in range(n):
    if i+1<n and s_list[i]==1 and s_list[i+1]==1:
        ans+=1
    if i-1>=0 and s_list[i]==0 and s_list[i-1]==0:
        ans+=1
print(ans)

Submission status: Runtime Error

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

L_record = []
R_record = []

if s[0] == "L":
    flg = "R"
else:
    flg = "L"

for i, char in enumerate(s):
    if char == "L" and flg == "R":
        L_record.append([i, 1])
        flg = "L"
    elif char == "L" and flg == "L":
        L_record[-1][1] += 1
    elif char == "R" and flg == "L":
        R_record.append([i, 1])
        flg = "R"
    elif char == "R" and flg == "R":
        R_record[-1][1] += 1

L_record.sort(key=lambda x: (x[0]))
R_record.sort(key=lambda x: (x[0]))
#print(L_record, R_record)

if L_record[-1][0] + L_record[-1][1] == n:
    record = L_record.pop()
    L_record = [record] + L_record
if R_record[-1][0] + R_record[-1][1] == n:
    record = R_record.pop()
    R_record = [record] + R_record


point = 0
for i, char in enumerate(s):
    #print(i, char)
    if char == "L" and i-1 >= 0:
        if s[i-1] == "L":
            point += 1
            #print(point)
    if char == "R" and i+1 < n:
        if s[i+1] == "R":
            point += 1
            #print(point)
#print(point)

#L -> R
point_l = point
for i in range(k):
    if L_record != []:
        idx, num = L_record.pop()
        if idx == 0:
            point_l += 1
        elif idx + num == n:
            point_l += 1
        else:
            point_l += 2

point_r = point
for i in range(k):
    if R_record != []:
        idx, num = R_record.pop()
        if idx == 0:
            point_r += 1
        elif idx + num == n:
            point_r += 1
        else:
            point_r += 2
print(max(point_r, point_l))

Submission status: Runtime Error

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

ans  = 0
tran = 0

for i in range(n):
    chk = s[i] + s[i+1]

    if chk == 'LR' or chk == 'RL':
        tran += 1
    else:
        ans += 1

if k*2 >= tran:
    print(n-1)
else:
    print(tran+(k*2))

Submission status: Runtime Error

Solution code:
import itertools
n, k = [int(i) for i in input().split()]
s = input()

status = s[0]
cnt = 1
sa = []
for i in range(1, n):
    if s[i] != status:
        sa.append(status * cnt)
        cnt = 0
        status = s[i]
    cnt += 1
sa.append(status * cnt)

for i in range(1, min(k*2, n), 2):
    sa[i] = ("R" if sa[i][0] == "L" else "L") * len(sa[i])

sa = ''.join(sa)

ans = 0
for i in range(n):
    if sa[i] == "L":
        if i > 0: 
            if sa[i-1] == "L": ans += 1
    else:
        if i < n-1:
            if sa[i+1] == "R": ans += 1

print(ans)

Submission status: Runtime Error

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

RL=0
LR=0

fo=0

if n<3:
  if n==1:
    print(0)
  else:
    print(1)
    
else:
  for i in range(n):
    if s[i]=='R' and i<n-1:
      if s[i+1]=='R':
        fo+=1
    if s[i]=='L' and 0<i:
      if s[i-1]=='L':
        fo+=1
        
    if i<n-1:
      if s[i]=='R' and s[i+1]=='L':
        RL+=1
      elif s[i]=='L' and s[i+1]=='R':
        LR+=1
        
  si=min(k,RL,LR)
  no=k-si
  LR_rest=LR-si
  RL_rest=RL-si
  if no==0:
    ans=fo+si*2
  else:
    ans=fo+si*2
    if s[0]=='L':
      if LR_rest>0:
        ans+=1
        LR_rest-=1
        no-=1
    if n0>0:
      if s[-1]=='R':
        if LR_rest>0:
          ans+=1
  print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
pre = s[0]
rsans = s[0]
first = s[0]

if s[0] == "R":
    second = "L"
else:
    second = "R"

for i in s[1:]:
    if i == second and k > 0:
        ans = ans + first
        pre = i
    elif i == first and pre == second:
        k -= 1
        ans = ans + i
        pre = i
    elif k == 0:
        ans = ans + i
    elif i == first and pre == first:
        ans = ans + i

pre = "0"
cnt = 0

for i in ans:
    if i == pre:
        cnt += 1
    pre = i

print(cnt)

Submission status: Runtime Error

Solution code:
import sys

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

lcnt=-1
rcnt=-1

rr=[0]*n
ll=[0]*n
sim=""
for si in s:
    if si=="R" and sim=="R":
        rr[rcnt]+=1
    elif si=="R" and sim!="R":
        rcnt+=1
        rr[rcnt]=1
    if si=="L" and sim=="L":
        ll[lcnt]+=1
    elif si=="L" and sim!="L":
        lcnt+=1
        ll[lcnt]=1
    sim=si
        

ll=[i for i in ll if i!=0]
rr=[i for i in rr if i!=0]
#print(ll)
#print(rr)

maxlen=max(len(ll),len(rr))
if maxlen<=k:
    print(n-1)
    sys.exit()
    
for i in range(k):
    ll[i]+=rr[i]
    rr[i]=0

for i in range(maxlen-1):
    if ll[i]!=0 and rr[i]==0 :
        ll[i+1]+=ll[i]
        ll[i]=0

icnt=0
for i in range(len(ll)):
    icnt+=max(ll[i]-1,0)
for i in range(len(rr)):
    icnt+=max(rr[i]-1,0)
    
print(icnt)

Submission status: Runtime Error

Solution code:
import sys

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

lcnt=-1
rcnt=-1

rr=[0]*n
ll=[0]*n
sim=""
for si in s:
#    print(si)
    if si=="R" and sim=="R":
        rr[rcnt]+=1
    elif si=="R" and sim!="R":
        rcnt+=1
        rr[rcnt]=1
    if si=="L" and sim=="L":
        ll[lcnt]+=1
    elif si=="L" and sim!="L":
        lcnt+=1
        ll[lcnt]=1
    sim=si
        

ll=[i for i in ll if i!=0]
rr=[i for i in rr if i!=0]
#print(ll)
#print(rr)

maxlen=max(len(ll),len(rr))
if maxlen<=k:
    print(n-1)
    sys.exit()
    
for i in range(k):
    ll[i]+=rr[i]
    rr[i]=0
#print(lr)
for i in range(maxlen-1):
    if ll[i]!=0 and rr[i]==0 :
        ll[i+1]+=ll[i]
        ll[i]=0
#print(lr)

icnt=0
for i in range(maxlen):
    icnt+=max(ll[i]-1,0)+max(rr[i]-1,0)
    
print(icnt)

Submission status: Runtime Error

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

s_=''
S_=[]

for s in S:
    if s != s_:
        S_.append(s)
        s_=s
        
    else:
        S_[-1]+=s
        

change_str_dict={'R':'L','L':'R'}
change_str=change_str_dict[S_[1][0]]

for m in range(1,min(2*M,len(S_)),2):
    S_[m]=change_str*len(S_[m])

S_=''.join(S_)
# print(S_)

s_=S_[0]
ans=0
for s in S_[1:]:
    if s == s_:
        ans+=1
    else:
        s_=s
        
print(ans)

Submission status: Runtime Error

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

ans = N - 1
initial = 0
for i in range(N-1):
    if S[i] == S[i+1]: initial += 1
ans = min(ans, initial + 2 * K)
print(ans)v

Submission status: Runtime Error

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

h = 0
for i in range(len(S)-1):
  if s[i] == S[i+1]:
    h += 1
h += 2*K
print(min(N-1, h))

Submission status: Runtime Error

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

#グループの
cnt = 1

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


print(N - max(1, cnt - 2*k))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = list(input())
    
e = s[0]
if e == 'L':
    p = 'R'
else:
    p = 'L'

l = 0
while 0 < k:
    while s[l] != p and l < n-1:
        l += 1
    s[l] = e
    r = l+1
    while r < n and s[r] == p:
        s[r] = e
        r +=1

    k -= 1
    l = r
    if l == n-1:
        break

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import ceil
N, K = mapint()
S = list(str(input()))

old = S[0]
lis = []
cnt = 1
for i in range(1, N):
    s = S[i]
    if s!=old:
        lis.append(cnt)
        old = s
        cnt = 1
    else:
        cnt += 1
lis.append(cnt)
for l in range(K):
    if len(lis)>=3:
        l1 = lis.pop()
        l2 = lis.pop()
        lis[-1] += (l1+l2)
    else:
        l1 = lis.pop()
        lis[-1] += l1
        break

ans = sum([i-1 for i in lis])
print(ans)

Submission status: Runtime Error

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

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

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

l_cnt=[]
for i in range(n):
  if s[i]=='R':
    if i==0:
      if s[i+1]=='L':
        l_cnt.append(1)
    if i==n-1:
      if s[i-1]=='L':
        l_cnt.append(1)
    else:
      t_l_cnt=s[i-1:i+2].count('L')
      l_cnt.append(t_l_cnt)

r_cnt=[]
for i in range(n):
  if s[i]=='L':
    if i==0:
      if s[i+1]=='R':
        r_cnt.append(1)
    if i==n-1:
      if s[i-1]=='R':
        r_cnt.append(1)
    else:
      t_r_cnt=s[i-1:i+2].count('R')
      r_cnt.append(t_r_cnt)

ans=l_cnt+r_cnt
ans.sort(reverse=True)
ans=sum(ans[:k])

print(happy+ans)

Submission status: Runtime Error

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

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

l_cnt=[]
for i in range(n):
  if s[i]=='R':
    if i==0:
      if s[i+1]=='L':
        l_cnt.append(1)
    if i==n-1:
      if s[i-1]=='L':
        l_cnt.append(1)
    else:
      t_l_cnt=s[i-1:i+2].count('L')
      l_cnt.append(t_l_cnt)
l_cnt.sort(reverse=True)
ans_l=sum(l_cnt[:k])

r_cnt=[]
for i in range(n):
  if s[i]=='L':
    if i==0:
      if s[i+1]=='R':
        r_cnt.append(1)
    if i==n-1:
      if s[i-1]=='R':
        r_cnt.append(1)
    else:
      t_r_cnt=s[i-1:i+2].count('R')
      r_cnt.append(t_r_cnt)
r_cnt.sort(reverse=True)
ans_r=sum(r_cnt[:k])

print(happy+max(ans_l,ans_r))

Submission status: Runtime Error

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

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

rl = 0
lr = 0

for i in range(1,n-1):
    if s[i] == "L":
        if s[i-1] == "L":
            hap += 1
        else:
            rl += 1
    else:
        if s[i+1] == "R":
            hap += 1
        if s[i-1] == "L":
            lr += 1

tmp = min(rl,lr,k)
hap += 2 * tmp

if rl != lr and k - tmp >0:
    hap += 1
print(hap)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N, K = zz()
S = S()
change_points = [0]
if (S[0] == S[1] == 'R'):
    ans = 1
else:
    ans = 0
for i in range(1, N):
    if S[i] == 'L':
        if (S[i - 1] == 'L'):
            ans += 1
    else:
        if (i == N - 1):
            pass
        elif (S[i + 1] == 'R'):
            ans += 1

    if (S[i] != S[i - 1]):
        change_points.append(i)
# print(change_points)
# print(ans)
ans += (2*K)

print(min(ans, N-1))

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split())
score,d,cd = 0,None,0
for i,l in enumerate(raw_input()):
	if d != l:
		cd +=1
		d = l
	if i and s[i-1] == s[i]:  score += 1


if cd > 2:
	t = min(k,((cd - 2)+1)/2)
	k -= t
	score += 2 * t 
	cd -= 2 * t
if cd == 2 and k:
	score +=1
	cd -= 1
print score

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split())
s = raw_input()
cd = 0
d = None
for i,l in enumerate(s):
	if d != l:
		cd +=1
		d = l
	if i and s[i-1] == s[i]: score += 1
	

if cd > 2:
	t = min(k,((cd - 2)+1)/2)
	k -= t
	score += 2 * t 
	cd -= 2 * t
if cd == 2 and k:
	score +=1
	cd -= 1
print score

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product


def solve():
    n, k = MI()

    S = list(input())

    A = []
    # print(S)
    cnt = 0
    pre = ''
    for s in S:
        if pre == s:
            cnt += 1
        else:
            if cnt:
                A.append((pre, cnt))
            pre = s
            cnt = 1
    if cnt:
        A.append((pre, cnt))
    # print('A', A)

    target = 'L'
    rev = 'R'
    ans = 0
    for _ in range(2):
        B = A.copy()
        T = []
        for idx, (b, cnt) in enumerate(B):
            if b == target:
                l = 0
                r = 0
                if idx - 1 >= 0:
                    l = B[idx-1][1]
                if idx + 1 < len(B):
                    r = B[idx+1][1]

                T.append((idx, l + cnt + r, cnt))

        T = sorted(T, key=lambda x: x[1], reverse=True)
        # print('T', T)

        q = deque(T)
        for _ in range(k):
            idx, _, cnt = q.popleft()
            B[idx] = (rev, cnt)

        res = 0
        sm = 0
        pre = ''
        for (b, cnt) in B:
            if pre == b:
                sm += cnt
            else:
                if sm > 1:
                    res += sm - 1
                sm = cnt
                pre = b
        if sm > 1:
            res += sm - 1

        # print('B', B)
        # print(res)
        ans = max(res, ans)
        target = 'R'
        rev = 'L'
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from itertools import groupby

# RUN LENGTH ENCODING
def runLengthEncode(S: str):
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, str(len(list(v)))))
    return res

def runLengthdecode(L: "list[tuple]"):
    res = ""
    for c, n in L:
        res += c * int(n)
    return res

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    S = input()
    compressed = runLengthEncode(S)

    # ある区間を反転させるとその両端が前後で連結するようにするのが最大化できる = 両端の操作は損
    for k in range(K):
        i = 2 * k + 1   # 奇数インデックスのみ反転させる。
        compressed[i] = ('L', compressed[i][1]) if compressed[i][0] == "R" else ('R', compressed[i][1])

    reCompressed = runLengthEncode(runLengthdecode(compressed))
    ans = N - len(reCompressed)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=input()
c=0
d=0
for i in range(n):
    if S[i]==S[i+1]:
        c+=1
    if S[i]!=S[i+1]:
        d+=1
print(c+2*k-1 if d<=k and S[0]==S[-1] else c+2*k)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from Tools.scripts.highlight import ansi_highlight
N, K = map(int, input().split())
S = str(input())

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

Submission status: Runtime Error

Solution code:

h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res, length[i][j])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=input()
if n==2:
    print(1)
elif n==3:
    print(2)
score=0
count2=0
count1=0
for i in range(1,n-2):
    if s[i]!=s[i+1]:
        count2+=1
    else:
        score+=1

if s[0]!=s[1]:
    count1+=1
else:
    score+=1
if s[-1]!=s[-2]:
    count1+=1
else:
    score+=1
    
if count2<=k:
    score+=2*count2
    k-=count2
    score+=min(count1,k)
else:
    score+=2*k
    
print(score)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
def rle(s):#計算量N
    c = 0
    tmp, count, ans = s[0], 1, []
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            ans.append((-1)*count)
            c += count-1
            count = 1
            tmp = s[i]
    if count > 1:
        ans.append(count*(-1))
        c += count-1
    return ans,c #最大2N文字
N,K = map(int,input().split())
S = input()
ans,c = rle(S)
n = len(ans)
import heapq
heapq.heapify(ans)
MIN = min(n.K)
for i in range(MIN):

    a = heapq.heappop(ans)
    c += 2
if c >= N:
    c = N-1
print(c)

Submission status: Runtime Error

Solution code:
def rle(s):#計算量N
    c = 0
    tmp, count, ans = s[0], 1, []
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            ans.append((-1)*count)
            c += count-1
            count = 1
            tmp = s[i]
    if count > 1:
        ans.append(count*(-1))
        c += count-1
    return ans,c #最大2N文字
N,K = map(int,input().split())
S = input()
ans,c = rle(S)
import heapq
heapq.heapify(ans)
for i in range(K):
    a = heapq.heappop(ans)
    c += 2
if c >= N:
    c = N-1
print(c)

Submission status: Runtime Error

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

def syukuyaku(S):
    if len(S) <= 1:
        return S
    res = S[0]
    cnt = 0
    i = 0
    while i < len(S)-1:
        if S[i] == S[i+1]:
            while i < len(S)-1 and S[i] == S[i+1]:
                cnt += 1
                i += 1
        else:
            i += 1
            res += S[i]
    return res, cnt

S_ ,cnt = syukuyaku(S)

if S_.count("L") == S_.count("R"):
    if S_.count("L") <= K:
        print(cnt + S_.count("L")*2)
    else:
        print(cnt + K * 2)
elif S_.count("L") > S_.count("R"):
    if S_.count("L") <= K:
        print(len(S)-1)
    else:
        print(cnt + K * 2)
else:
    if S_.count("R") <= K:
        print(len(S)-1)
    else:
        print(cnt + K * 2)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = input()
lr_cnt = 0
rl_cnt = 0
mnt = 0
for i in range(len(s)-1):
    if s[i] == 'L' and s[i+1] == 'R':
        lr_cnt += 1
        
    if s[i] == 'R' and s[i+1] == 'L':
        rl_cnt += 1
mnt  = rl_cnt + lr_cnt+1
mnt = np.max([1,mnt-2*k])
if mnt == 1:
    print(n-1)
else:
    print(n-rl_cnt-lr_cnt+2*k-1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = list(input())
R = []
L = []
flag = 1 #1...R 0...L
lf = 1
rf = 1
if s[0]=="L":
    flag = 0
    lf = 0
if s[-1]=="L":
    rf = 0
count = 1
for i in range(n):
    if i==n-1:
        if flag==1:
            R.append(count*(-1))
            break
        else:
            L.append(count*(-1))
            break
    if s[i]==s[i+1]:
        count += 1
    elif flag==1:
        R.append(count*(-1))
        flag = 0
        count = 1
    else:
        L.append(count*(-1))
        flag = 1
        count = 1

import heapq
ans = 0
if s.count("R")>s.count("L"):
    ans += sum(R)*(-1)-len(R)
    copy_L = [x for x in L]
    heapq.heapify(L)
    for i in range(k):
        x = heapq.heappop(L)
        if lf==0 and x==copy_L[0] and copy_L.count(x)==1:
            ans += x*(-1)
        elif rf==0 and x==copy_L[-1] and copy_L.count(x)==1:
            ans += x*(-1)
        else:
            ans += x*(-1) +1
else:
    ans += sum(L)*(-1)-len(L)
    copy_R = [x for x in R]
    heapq.heapify(R)
    for i in range(k):
        x = heapq.heappop(R)
        if lf==1 and x==copy_R[0] and copy_R.count(x)==1:
            ans += x*(-1)
        elif rf==1 and x==copy_R[-1] and copy_R.count(x)==1:
            ans += x*(-1)
        else:
            ans += x*(-1) + 1 

print(ans)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(10)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	io_init;
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;
	vector<pair<int,string>> p;
	for (int r = 0, l = 0; r < N; r++) {
		if (S[l] != S[r]) {
			p.push_back({ p.size(), S.substr(l, r - l) });
			l = r;
		}
		if (r == N - 1) {
			p.push_back({ p.size(),S.substr(l, r - l + 1) });
		}
	}
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		if (S[i] == 'R' && S[i] == S[i + 1])ans++;
	}
	for (int i = N - 1; i > 0; i--) {
		if (S[i] == 'L' && S[i] == S[i - 1])ans++;
	}
	for (int i = 0; i < p.size() - 1; i++) {
		if (K != 0) {
			K--;
			ans += 2;
		}
	}
	if (K != 0) {
		ans += min(K, 2);
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
def swap():
  N,K = map(int,input().split())
  S = list(input())
  l = 0
  r = N - 1
  ans = 0
  while K > 0:
    for i in range(0,N - 1):
      if S[i] != S[i + 1]:
        left = i + 1
        break
    for j in range(N - 1,-1,-1):
      if S[j] != S[j - 1]:
        right = j
        break
    if left == right:
      right = N
    for i in range(left,right):
      s = S[i]
      if s == "L":
        S[i] = "R"
      else:
        S[i] = "L"
    K -= 1
  
  for i in range(0,N):
    j = (-i - 1)
    if S[i] == "L" and S[i] == S[i - 1] and i > 0:
      ans += 1
    if S[j] == "R" and S[j + 1] == S[j] and i > 0:
      ans += 1

  print(ans)
  
swap()

Submission status: Runtime Error

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

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

two = 0
pre = s[0]
cont = 1
for c in s[1:]:
  if c != pre:
    if c == s[0]:
      two += 1
    ans += cont-1
    cont = 1
    pre = c
  else:
    cont += 1
ans += cont-1

if s[0] != s[1]:
  ans += 1
print(ans + 2*min(k,two))

Submission status: Runtime Error

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

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

pre = s[0]
cont = 1
for c in s[1:]:
  if c != pre:
    if c == s[0]:
      two += 1
    ans += cont-1
    cont = 1
    pre = c
  else:
    cont += 1
ans += cont-1

if s[0] != s[1]:
  ans += 1
print(ans + 2*min(k,two))

Submission status: Runtime Error

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

pre = s[0]
cont = 1
for c in s[1:]:
  if c != pre:
    if c == s[0]:
      two += 1
    ans += cont-1
    cont = 1
  else:
    cont += 1
ans += cont-1

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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)
 
ans=sum(A)-len(A)+(K)*2
 
if ans<N-1:
    print(ans)
else: print(N-1)