Problem:


Score : 400 points

Problem Statement

There are N people standing in a queue from west to east.

Given is a string S of length N representing the directions of the people.
The i-th person from the west is facing west if the i-th character of S is L, and east if that character of S is R.

A person is happy if the person in front of him/her is facing the same direction.
If no person is standing in front of a person, however, he/she is not happy.

You can perform the following operation any number of times between 0 and K (inclusive):

Operation: Choose integers l and r such that 1 \leq l \leq r \leq N, and rotate by 180 degrees the part of the queue: the l-th, (l+1)-th, ..., r-th persons. That is, for each i = 0, 1, ..., r-l, the (l + i)-th person from the west will stand the (r - i)-th from the west after the operation, facing east if he/she is facing west now, and vice versa.

What is the maximum possible number of happy people you can have?

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

|S| = N

Each character of S is L or R.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of happy people after at most K operations.

Sample Input 1

6 1
LRLRRL

Sample Output 1

3

If we choose (l, r) = (2, 5), we have LLLRLL, where the 2-nd, 3-rd, and 6-th persons from the west are happy.

Sample Input 2

13 3
LRRLRLRRLRLLR

Sample Output 2

9

Sample Input 3

10 1
LLLLLRRRRR

Sample Output 3

9

Sample Input 4

9 2
RRRLRLRLL

Sample Output 4

7



Sample input:
6 1
LRLRRL


Sample output:
3

Submission status: Runtime Error

Solution code:

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

S = input()

if N == 1:
    print(0)
    exit()
#左端をLにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "L" or ex == "") and S[i] == "R":
        start = i
    if ex == "R" and S[i] == "L":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr,N)
num = stack[tmp-1][1]
ss = "L"*(num+1)+S[num+1:]
ll = num

for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            ll += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1


#右からひっくり返す
tmp = min(K,num_substr,N)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"L"*(N-1-num)

lr = (N-1-num)

for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            lr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1


######################################################################
#左端をRにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "R" or ex == "") and S[i] == "L":
        start = i
    if ex == "L" and S[i] == "R":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr,N)
num = stack[tmp-1][1]
ss = "R"*(num+1)+S[num+1:]
rl = num
#print(ll, tmp)
for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rl += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1


#右からひっくり返す
tmp = min(K,num_substr,N)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"R"*(N-1-num)

rr = (N-1-num)
#print(ll, tmp)
for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1


print(max([ll,lr,rl,rr]))

Submission status: Runtime Error

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

a = []
temp = S[0]
hantei = False
s = []
n = []

for i in range(1, N):
    if hantei and temp != S[i]:
        s.append(a)
        n.append(len(a))
        a = []
    if temp != S[i] or hantei:
        hantei = True
        a.append(S[i])
        temp = S[i]

s.insert(0, list(S[0]))
s.append(list(S[-1]))
ans = 0
for i in range(K):
    ans = ans + 1 + max(n)
    k = n.index(max(n))
    n[k] = 0
print(ans)

Submission status: Runtime Error

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


def solve(N: int, K: int, S: str):
    S_list = list(S)
    L_num = 0
    R_num = 0
    small_num = 0
    popular_s = ''
    for i in S_list:
        if i == 'L':
            L_num += 1
        else:
            R_num += 1
    if L_num > R_num:
        popular_s = 'S'
        small_num = R_num
    else:
        popular_s = 'R'
        small_num = L_num

    if small_num <= K:
        print(N - 1)
    else:
        # ちゃんと解く
        a = []
        counter = -1
        result = 0
        before_s = ''
        for i in S_list:
            if i != popular_s:
                counter += 1
            else:
                a.append(counter)
                counter = 0
                if before_s == i:
                    result += 1
            before_s = i
        a.append(counter)

        #print(a)
        #print('tmp result', result)

        a_sorted = sorted(a)

        for i in range(K):
            b = a_sorted.pop()
            result += b + 1
        print(result)
    return


# Generated by 1.1.5 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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
    
    if S[0] =! S[1]:
        score += 1
        if K - mikomi > 1:
            if S[len(S)-2] != S[len(S)-1]:
                score += 1
    elif  if S[len(S)-2] != S[len(S)-1]:
        score += 1
    
else:
    score = orig_score + K*2


    
print(score)

Submission status: Runtime Error

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

count=0
tmp = ''
res = []
for s in S:
  if s != tmp:
    tmp = s
    if count != 0:
      res.append(count)
    count = 1
  else:
    count += 1

res.append(count)

nokori = K
count = 0
for i in K:
  num = res.count(i+1)
  if nokori - num * i < 0:
    count += nokori // i
    break
  else:
    count += nokori // i
    nokori -= nokori - num * i
    N - (len(res) - count)
print(N)

Submission status: Runtime Error

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

arra = list(input())
arr = arra[:]
count = []
count0 = 0
for i in range(len(arr)-1):
    if arr[i]==arr[i+1]:
        count0+=1
count.append(count0)

        
for _ in range(k):
    whl = [i for i, x in enumerate(arr) if x == 'L']
    whr = [i for i, x in enumerate(arr) if x == 'R']
    suma=[]
    for i in range(1,len(whl)-1):
        suma.append(whl[i+1]-whl[i-1])
    
    sumb=[]
    for i in range(1,len(whr)-1):
        sumb.append(whr[i+1]-whr[i-1])

    
    if len(suma)==0:
        suma = [0]
    if len(sumb)==0:
        sumb = [0]
        
    
    if max(suma) > max(sumb):
        na = suma.index(max(suma))
        
        arr[whl[na]+1:whl[na+2]] = arr[whl[na]+1:whl[na+2]][::-1]
        for i in range(whl[na]+1,whl[na+2]):
            if arr[i] == "L":
                arr[i] = "R"
            else:
                arr[i] = "L"

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

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

print(max(count))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
cnt1 = 0
cnt2 = 0
if len(S) == 1:
    print(0)
    exit()
p = 0
if 'L' == S[0]:
    for i in range(N):
        if 'L' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break
else:
    for i in range(N):
        if 'R' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break

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

ans.sort()
ans.reverse()

sums = 0
for i in range(N-1):
    if 'LL' == S[i:i+2]:
        sums += 1
    elif 'RR' == S[i:i+2]:
        sums += 1

if K >= len(ans):
    print(len(S) - 1)
else:
    if len(ans) == 0:
        print(len(S) - 1)
    if sums + sum(ans[:K]) >= len(S):
        print(len(S) - 1)
    else:
        print(sums + sum(ans[:K]))

Submission status: Runtime Error

Solution code:
str = input()
l = str.split()
N = int(l[0])
k = int(l[1])

direction = input()
happy = 0

def messi(dir):
    # consecutive part
    global happy
    part = [0, 0]
    preChar = 'A'
    max = 0
    count = 1
    startPoint = 0
    for i in range(len(dir)):
        if dir[i] == preChar:
            count += 1
        else:
            if preChar == 'A':
                count -= 1
            preChar = dir[i]
            if count > max:
                part = [startPoint, i-1]
                max = count
            count = 1
            startPoint = i
    if preChar == 'A':
        count -= 1
    if count > max:
        part = [startPoint, len(dir)]
        max = count
    happy = max
    return part

def suarez(dir):
    part = messi(dir)
    for i in range(part[0], part[1]+1):
        if dir[i] == 'R':
            dir = dir[:i] + 'L' + dir[i+1:]
        else:
            dir = dir[:i] + 'R' + dir[i+1:]

    return dir

for i in range(k):
    direction = suarez(direction)
part = messi(direction)
print(happy)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:

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

S = input()

if N == 1:
    print(0)
    exit()
#左端をLにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "L" or ex == "") and S[i] == "R":
        start = i
    if ex == "R" and S[i] == "L":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "L"*(num+1)+S[num+1:]
ll = num

for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            ll += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"L"*(N-1-num)

lr = (N-1-num)

for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            lr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1


######################################################################
#左端をRにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "R" or ex == "") and S[i] == "L":
        start = i
    if ex == "L" and S[i] == "R":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "R"*(num+1)+S[num+1:]
rl = num
#print(ll, tmp)
for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rl += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"R"*(N-1-num)

rr = (N-1-num)
#print(ll, tmp)
for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1


print(max([ll,lr,rl,rr]))

Submission status: Runtime Error

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

def f1(s, l, r):
  return s[:l] + f2(s[l:r + 1]) + s[r + 1]

def f2(s):
  t = list(s)
  t.reverse()
  return ''.join('R' if c == 'L' else 'L' for c in t)

def f3(s):
  before = s[0]
  result = 0
  for i in range(1, N):
    if s[i] == before:
      result += 1
    else:
       before = s[i]
  return result

def f4(s, c):
  lstart = -1
  llen = 0
  tstart = -1
  for i in range(N):
    if s[i] == c and tstart == -1:
      tstart = i
    if s[i] != c and tstart != -1:
      tlen = i - tstart
      if tlen > llen:
        lstart = tstart
        llen = tlen
  return (lstart, llen)

for _ in range(K):
  lstart, llen = f4(S, 'L')
  rstart, rlen = f4(S, 'R')
  if lstart < rstart:
    S = f2(S, lstart + llen, rstart + rlen - 1)
  else:
    S = f2(S, rstart + rlen, lstart + llen - 1)
  if lstart == -1 or rstart == -1:
    break

print(f3(S))

Submission status: Runtime Error

Solution code:

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

S = input()

#左端をLにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "L" or ex == "") and S[i] == "R":
        start = i
    if ex == "R" and S[i] == "L":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "L"*(num+1)+S[num+1:]
ll = num

for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            ll += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"L"*(N-1-num)

lr = (N-1-num)

for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            lr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1


######################################################################
#左端をRにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "R" or ex == "") and S[i] == "L":
        start = i
    if ex == "L" and S[i] == "R":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "R"*(num+1)+S[num+1:]
rl = num
#print(ll, tmp)
for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rl += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"R"*(N-1-num)

rr = (N-1-num)
#print(ll, tmp)
for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1


print(max([ll,lr,rl,rr]))

Submission status: Runtime Error

Solution code:
def d(s, type):
    first_index = None
    last_index = None
    for i in range(0, n-1):
        if first_index == None:
            if s[i] != type:
                first_index = i
                if s[len(s)-1] != type:
                    last_index = len(s)-1
                    break
        if s[i] != type and s[i+1] == type:
            last_index = i
    if last_index == None and first_index != None:
        last_index = len(s)-1
    return first_index, last_index


def find(n, k, s):
    f1, l1 = d(s, "R")
    f2, l2 = d(s, "L")

    valid1 = f1 is not None and l1 is not None
    valid2 = f2 is not None and l2 is not None

    if not valid2:
        return f1, l1

    if not valid1:
        return f2, l2

    if (l2 - f2) < (l1 - f1):
        return f2, l2
    else:
        return f1, l1


def o(s):
    if s == "L":
        return "R"
    else:
        return "L"


def turn(list, first_index, last_index):
    for i in range(last_index-first_index):
        l = first_index+i
        r = last_index-i
        if l > r:
            break
        org_l = list[l]
        org_r = list[r]
        list[l] = o(org_r)
        list[r] = o(org_l)


def calc(list):
    r = 0
    for i in range(len(list)):
        if list[i] == "R" and i < len(list)-1:
            if list[i] == list[i+1]:
                r += 1
        if list[i] == "L" and i >= 1:
            if list[i] == list[i-1]:
                r += 1
    return r


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

for _ in range(k):
    first_index, last_index = find(n, k, s)
    turn(s, first_index, last_index)

print(calc(s))

Submission status: Runtime Error

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

l = []

i = 0
last = "H"
cnt = 1
while 1:
    if (i>=len(s)):
        break
    if (last == s[i]):
        cnt +=1
    else:
        l.append(cnt)
        cnt = 1
        last = s[i]
    i+=1

t = sorted(l, reverse=True)
ans = 0
for i in range(k+1):
    ans+=t[i]

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = input()
ans = 0
count = 0
for i in range(1,n-1):
    if s[i] == "L" and s[i-1] == "L":
        ans += 1
    elif s[i] == "R" and s[i+1] == "R":
        ans += 1
    if s[i] == "R" and s[i+1] == "L":
        count += 1
    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: Runtime Error

Solution code:
def change(S,l,r):
    p = 0
    V = S[l:r]
    list = []
    for q in V:
        list.insert(0,q)
    for p in range(l,r+1):
        if list[p-l-1] == "L":
            S[p-1] == "R"
        else:
            S[p-1] = "L"

def check(S,N):
    counta = 0
    for t in range(0,N-1):
        if S[t] == S[t+1]:
            counta += 1
    print(counta)

def beauty(N,K,S):
    for i in range(0,K):
        for j in range(0,N):
            if S[j+1] != S[j]:
                l = j+1
                break
        for k in range(0,N)[::-1]:
            if S[k] != S[k-1]:
                r = k
                break
        change(S,l,r)
    check(S,N)

N,K = (int(x) for x in input().split())
S = list(input())
beauty(N,K,S)

Submission status: Runtime Error

Solution code:
def change(S,l,r):
    p = 0
    V = S[l:r]
    list = []
    for q in V:
        list.insert(0,q)
    for p in range(l,r+1):
        if list[p-l-1] == "L":
            S[p-1] == "R"
        else:
            S[p-1] = "L"

def check(S,N):
    counta = 0
    for t in range(0,N-1):
        if S[t] == S[t+1]:
            counta += 1
    print(counta)

def beauty(N,K,S):
    for i in range(0,K):
        for j in range(0,N):
            if S[j+1] != S[j]:
                l = j+1
                break
        for k in range(0,N)[::-1]:
            if S[k] != S[k-1]:
                r = k
                break
        change(S,l,r)
    check(S,N)

N,K = (int(x) for x in input().split())
S = list(input())
beauty(N,K,S)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
cnt1 = 0
cnt2 = 0
if len(S) == 1:
    print(0)
    exit()
p = 0
if 'L' == S[0]:
    for i in range(N):
        if 'L' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break
else:
    for i in range(N):
        if 'R' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break

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

ans.sort()
ans.reverse()

sums = 0
for i in range(N-1):
    if 'LL' == S[i:i+2]:
        sums += 1
    elif 'RR' == S[i:i+2]:
        sums += 1

if K >= len(ans):
    print(len(S) - 1)
else:
    if sums + sum(ans[:K]) >= len(S):
        print(len(S) - 1)
    else:
        print(sums + sum(ans[:K]))

Submission status: Runtime Error

Solution code:
N, 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(max(len(cs) - 2 * M + 1, 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: Runtime Error

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

cur = S[0]
n = 1
n_l = []
for s in S[1:]:
    if s == cur:
        n += 1
    else:
        n_l.append(n)
        n = 1
    cur = s
n_l.append(n)
#print(n_l)

for _ in range(K):
    if len(n_l) > 3:
        max1, max2 = sorted(n_l[1:-1], reverse=True)[:2]
        n_max1 = n_l[1:-1].index(max1) + 1
        n_l_ = n_l[:]
        n_l_[n_max1] = -1
        n_max2 = n_l_[1:-1].index(max1) + 1
        l, r = min(n_max1, n_max2), max(n_max1, n_max2)
        n_l = n_l[:l-1] + [n_l[l-1]+n_l[l]] + n_l[l+1:r] + [n_l[r]+n_l[r+1]] + n_l[r+2:]
        #print(n_l)
    else:
        n_l = [sum(n_l)]
print(sum(n_l)-len(n_l))

Submission status: Runtime Error

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

        if ''.join(s) == s:
            break
        else:
            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: Runtime Error

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

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

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

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

print(init + (2 * k))

Submission status: Runtime Error

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

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

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

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

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

    print(kohuku)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import sys
import itertools
n, K = map(int, input().split())
S = list(input())

def main(S, score):
    L =[]
    for i in range(n):
        if S[i] =='R':
            L.append(i)
    L = list(itertools.combinations(L, 2))
    cnt = 0
    m = []
    for l in L:
        if cnt < S[l[0]:l[1]+1].count('R'):
            cnt = S[l[0]:l[1]+1].count('R')
            m = l
    M = S[m[0]:m[1]+1:]
    M = M[::-1]
    for i in range(len(M)):
        if M[i] == 'R':
            M[i] = 'L'
        elif M[i] == 'L':
            M[i] = 'R'
    S = S[0:m[0]] + M + S[m[1]+1:]

    ten = 0
    for i in range(n-1):
        if S[i] == S[i+1]:
            ten+=1
    if score < ten:
        score = ten
    return S, score
score = 0
for k in range(K):
    S, score = main(S, score)
    #print(S)
print(score)

Submission status: Runtime Error

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

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

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

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

print(init + (2 * k))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = 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)
        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))