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:
N,K = map(int, input().split())
S = list(input())
numL = S.count("L")
numR = S.count("R")

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

if K >= (turning + 2) // 2:
	print(N-1)
else:
	print(score + 2*K)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
g=0
for i in range(n):
    if i!=0:
        if s[i-1]==s[i] and s[i]=="L":
            g+=1
    if i!=n-1:
        if s[i+1]==s[i] and s[i]=="R":
            g+=1
print(min(n-1,g+2*k))

Submission status: Accepted

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

s = input()

#if n ==1:
#    print(0)
#    sys.exit()

ans = n-1
tmp = 0
for i in range(n-1):
    if s[i] != s[i+1]:
        ans -= 1
        
ans += 2*k
print(min(ans,n-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, K = LI()
    S = SI()

    wakareme = []
    current_koufuku = 0
    for i in range(N-1):
        if S[i] != S[i+1]:
            wakareme.append(i)
        else:
            current_koufuku += 1

    if 2*K < len(wakareme):
        print(current_koufuku + 2 * K)  # K 回の操作すべてで幸福を+2できる。
        return
    else:
        print(N-1)  # 末端以外の人すべてを幸福にできる。
        return


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
a=[]
for i in range(n):
    if(s[i]=="L"):
        a.append(-1)
    else:
        a.append(1)
gen=0
for i in range(n):
    num=i+a[i]
    if(num>=0 and num <=n-1):
        if(a[i]*a[num]==1):
            gen+=1

ans=gen+k*2
if(ans>=n):
    ans=n-1
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
unhappy = s.count('RL')+s.count('LR')
happy = n-unhappy-1
happy = min(n-1,happy+2*k)
print(happy)

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############
N,K = ip()
S = input()
l = []

c = 1
for i in range(1,N):
    if S[i] == S[i-1]:
        c+=1
    else:
        l.append(c)
        c=1
l.append(c)

ans = 0
K *= 2
ans += l[0]-1
for i in l[1:]:
    if K>0:
        K-=1
        ans+=i
    else:
        ans+=i-1
print(ans)

Submission status: Accepted

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


from itertools import groupby

#ans=0

gs=[len(list(group)) for key,group in groupby(S)]
now_ans = N-len(gs)
add_ans = now_ans + 2*K

ans=min(add_ans,N-1)




print(str(ans))

Submission status: Accepted

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


def solve(N: int, K: int, S: str):
    counter = 0
    for i, s in enumerate(S):
        if i > 0:
            if s == 'L' and S[i-1] == 'L':
                counter += 1
        if i < N-1:
            if s == 'R' and S[i+1] == 'R':
                counter += 1
    n = N - counter
    print(N - max(1, n - 2 * K))
    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: Accepted

Solution code:
import sys; from collections import deque ; readline = sys.stdin.readline

N, K = map(int, readline().split())
S = readline().rstrip()

nhappy = 0
nseg = 0

state = None
for c in S:
    if c == state:
        nhappy += 1
    else:
        nseg += 1
        state = c

k = K
while k > 0:
    k -= 1
    if nseg >= 3:
        nseg -= 2
        nhappy += 2
    elif nseg == 2:
        nseg -= 1
        nhappy += 1
    else:
        break

print(nhappy)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

p = 0
ans = 0
i = 0
m = 0
while i < N:
    l = 1
    while i + l < N and S[i] == S[i + l]:
        l += 1
    ans += l - 1
    if p >= 2 and m < K:
        ans += 2
        p -= 2
        m += 1
    p += 1
    i += l
if m < K and p >= 2:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
"""
N = int(input())
A, B = map(int,input().split())
lst = [list(map(int,input().split())) for i in range(M)]
A = list(map(int,input().split()))
"""

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

pre_dire = S[0]
n_boundary = 0
ans = 0
for i in range(1,N):
  if S[i] == pre_dire:
    ans += 1
  else:
    pre_dire = S[i]
    n_boundary += 1
    
#print(n_boundary)
#print(ans)

for i in range(K):
  if n_boundary >= 2:
    ans += 2
    n_boundary -= 2
  elif n_boundary > 0:
    ans += 1
    n_boundary -= 1
  elif n_boundary == 0:
    break

print(ans)

Submission status: Accepted

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

bef = s[0]
temp = 0

# if s[0] != "L":
#     comp.append(0)
#
# if s[-1] != "L":
#     comp.append(0)

for c in s:
    if c == bef:
        temp += 1
    else:
        comp.append(temp)
        temp = 1
        bef = c
comp.append(temp)

init = 0
n = len(comp)
for c in comp:
    init += c-1

inside = 0
if n%2 == 0:
    inside = n//2-1
else:
    inside = n//2

outside = 0

if n%2 == 0:
    outside = 1
else:
    outside = 0

tot = inside+outside

if k >= tot:
    print(sum(comp)-1)
elif k > inside:
    print(init+2*inside+outside)
else:
    print(init+2*k)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, S: str):

    seq = []
    ans = 1
    for i in range(N-1):
        if S[i] == S[i+1]:
            ans += 1
        else:
            seq.append(ans)
            ans = 1
    # 最後
    if S[N-2] == S[N-1]:
        seq.append(ans)
    else:
        seq.append(1)
    # print(seq)

    if len(seq) - 2*K <= 1:
        print(N-1)
    else:
        ans = 0
        for c in seq:
            ans += c-1
        print(ans+2*K)
    return


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

Solution code:
n,m=map(int,input().split())
hoge=list(input())
ans=0
A=hoge[0]
for i in range(n-1):
  B=hoge[i+1]
  if(A==B):
    ans+=1
  A=B
print(min(n-1,ans+m*2))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
K = K*2
S = input()
LR = []
pre = S[0]
l = 1
for s in S[1:]:
    if pre != s:
        pre = s
        if K > 0:
            K -= 1
            l += 1
            continue
        LR.append(l)
        l = 1
        continue
    l += 1
LR.append(l)
ans = sum(map(lambda x: x-1, LR))

print(ans)

Submission status: Accepted

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

seq = 0
pre = ""
lr_num = []
for i in s:
    if i == pre:
        seq += 1
    else : 
        pre = i
        lr_num.append(seq)
        seq = 0
lr_num.append(seq)
lr_sum = sum(lr_num)
lr_len = len(lr_num)-1
if lr_len%2 == 1:
    print(lr_sum + 2*min(k,lr_len//2))
else:
    if k >= lr_len//2:
        print(lr_sum + 2*lr_len//2 -1 )
    else:
        print(lr_sum + 2*k)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(input())
i = 1
if N == 1:
    print(0)
    exit()
while K >= 1 and i < N:
    if S[i] != S[0]:
        while i<N and S[i] != S[0]:
            S[i] = S[0]
            i += 1
        K -= 1
    i += 1
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
if S[0] == "R" and S[1] == S[0]:
    ans += 1
if S[-1] == "L" and S[-2] == S[-1]:
    ans += 1
print(ans)

Submission status: Accepted

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

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

turn = N - happy - 1

for i in range(K):
    if turn <= 0:
        break
    elif turn == 1:
        happy += 1
        turn -= 1
    else:
        happy += 2
        turn -= 2

print(happy)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n,k=LI()
s=list(input())

ans=0
dif=0
for i in range(n-1):
    if s[i]!=s[i+1]:
        dif+=1
        
    if s[i]=='R' and s[i+1]=='R':
        ans+=1
    if s[i+1]=='L' and s[i]=='L':
        ans+=1
'''
#ans-=dif-2*k
print(dif)
print(dif-2*k)
print(ans)
'''
print(min(ans+2*k,n-1))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s="R"+input()+"L"
now="X"
l=[]
le=None
for i in range(n+2):
    if now!=s[i]:
        l.append(le)
        now=s[i]
        le=1
    else:
        le+=1
l.append(le)
l=l[1:]
nn=len(l)
lr=[]
ll=[]
su=0
for i in range(0,nn,2):
    lr.append(l[i])
    su+=l[i]-1
for i in range(1,nn,2):
    ll.append(l[i])
    su+=l[i]-1
if lr[0]>1:
    su-=1
if ll[-1]>1:
    su-=1
maxgain=n-1-su
if 2*k<maxgain:
    print(su+2*k)
else:
    print(su+maxgain)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

point = 0
before = 0
for i in li:
    if before == i:
        point += 1
    before = i
print(min(n-1, point + (k * 2)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
s=input().rstrip()
count=0
for i in range(n):
    if s[i]=='L' and i>=1:
        if s[i-1]=='L':
            count+=1
    elif s[i]=='R' and i<=n-2:
        if s[i+1]=='R':
            count+=1
Max=n-1
ans=count
for i in range(k):
    ans=min(ans+2,Max)
print(ans)

Submission status: Accepted

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

prev = ''
h = 0
for c in s:
    if c == prev:
        h += 1
    prev = c
print(min(h + 2 * k, n - 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

tmp = S[0]
ans = 0

for i in range(1, N):
    if tmp == S[i]:
        ans += 1
    tmp = S[i]

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

Submission status: Accepted

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

n = 0
p = "0"
for s in S:
    if s!=p: n+=1
    p = s

print(N-max(1,n-K*2))

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    
    count = sum(c == d for c, d in zip(S, S[1:]))
    count += 2 * K
    print(min(count, N - 1))


main()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
s = input()
list_s = [s[i] for i in range (len(s))]

if n==1:
  print(0)
else:#変わり目数を求める
  kaw = 0
  for i in range(n-1):
    if list_s[i+1]!=list_s[i]:
      kaw += 1
  ans = n-1-kaw+2*k
  print(min(ans,n-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    N, K = mi()
    S = li()
    count = 1
    ss = []
    for i in range(N):
        if i == N - 1:
            ss.append((S[i], count))
            break
        if S[i] == S[i + 1]:
            count += 1
        if S[i] != S[i + 1]:
            ss.append((S[i], count))
            count = 1
    # print(ss)
    cntL = 0
    cntR = 0
    for s, i in ss:
        if s == "L":
            cntL += 1
        else:
            cntR += 1
    # print(cntL, cntR)
    if K >= min(cntL, cntR):
        print(N - 1)
    else:
        print(N - len(ss) + 2 * K)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N-1):
    if S[i]==S[i+1]:
        total+=1
    else:
        count+=1
if K*2>=count:
    print(total+count)
else:
    print(total+K*2)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
hap=0
if(n>1):
  for i in range(n):
    if(i==0):
      if(s[0]==s[1]=='R'):
        hap+=1
    elif(i==n-1):
      if(s[n-2]==s[n-1]=='L'):
        hap+=1
    else:
      if(s[i]==s[i+1]=='R' or s[i-1]==s[i]=='L'):
        hap+=1
print(min(hap+2*k,n-1))

Submission status: Accepted

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

cnt_b = sum([(S[i] != S[i + 1]) for i in range(N - 1)])
    
if cnt_b < 2 * K:
    cnt_a = 0
else:
    cnt_a = cnt_b - 2 * K

# print("#", N, cnt_b, cnt_a)
print(max(0, N - (cnt_a + 1)))

Submission status: Accepted

Solution code:
N,K=[int(i) for i in input().split()]
S=list(input())
gun=1
prev=S[0]
for s in S:
  if s!=prev:
    gun+=1
  prev=s
fukou=max(1,gun-2*K)
print(N-fukou)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N,K = map(int, input().split())
Sn = str(input())
Rn = [0]
for i in range(1,N):
  if Sn[i] == Sn[i-1]:
    Rn[-1] += 1
  else:
    Rn.append(0)
Rn.sort(reverse=True)

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

Submission status: Accepted

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

Submission status: Accepted

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

#n_l,n_r, n
S_ = []

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



ans = sum([n-1 for n in S_]) + min(2*K, len(S_)-1)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
C = []
p = S[0]
cur = 0
for c in S:
    if c == p:
        cur += 1
    else:
        C.append(cur)
        cur = 1
        p = c
if cur:
    C.append(cur)
ans = sum(e-1 for e in C)
l = len(C) // 2
if len(C) % 2:
    ans += min(K, l) * 2
else:
    if K >= l:
        ans = N-1
    else:
        ans += min(K, l) * 2
print(ans)

Submission status: Accepted

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

cnt = 0
pre = s[0]
for ss in s[1:]:
	if ss != pre:
		cnt += 1
	pre = ss

cnt = max(0, cnt - 2 * k)

print(n - 1 - cnt)

Submission status: Accepted

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
ans += 2 * k
if ans < n:
    print(ans)
else:
    print(n-1)

Submission status: Accepted

Solution code:

N,K = map(int,input().split())
S = input()
same = 0
diff = 0
for n in range(1,N):
    if S[n]==S[n-1]:
        same+=1
    else:
        diff+=1

print(same+min(K*2, diff))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline().strip()

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

total_loss = 1

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
K += K
ans = 0
for i in range(1, N):
    if S[i - 1] == S[i]: #同じ時
        ans += 1
    else:
        if K > 0: #ひっくり返せる時
            K -= 1
            ans += 1

print (ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC140
import sys
#sys.setrecursionlimit(100000)

#n=int(input())
tmp = input().split()
n,k = list(map(lambda a: int(a), tmp))
s=input()


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

count+=k*2

if(count>=n):
	count=n-1

print(count)

Submission status: Accepted

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

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

print(cnt[0] + min(2 * k, cnt[1]))

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
S = sys.stdin.readline().rstrip()


def count(s):
    ret = 0
    k = K * 2
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            ret += 1
        elif k > 0:
            k -= 1
            ret += 1
    return ret


a = count(S)
print(a)

Submission status: Accepted

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

Submission status: Accepted

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

n_katamari = 1

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

n_katamari -= 2 * k
if n_katamari < 1:
	n_katamari = 1 

print(n - n_katamari)

Submission status: Accepted

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

prev = s[0]
cnt = 0
hoge = []
for i in range(n):
    if s[i] == prev:
        cnt += 1
    else:
        hoge.append((cnt, prev))
        cnt = 1
        prev = s[i]
hoge.append((cnt, prev))
#print(hoge)
m = len(hoge)
# 必要なのはこれで十分
k = min(k, m//2)
# oxoxo oxoxox xを回せば良い
ans = []
for i, (cnt, si) in enumerate(hoge):
    if i % 2 == 1 and (i+1)//2 <= k:
        if si=="L":
            ans += ["R"]*cnt
        else:
            ans += ["L"]*cnt
    else:
        ans += [si]*cnt

#print(ans)
ret = 0
for i in range(n):
    if ans[i] == "L" and i-1>=0 and ans[i-1] == "L":
        ret += 1
    elif ans[i] == "R" and i+1<n and ans[i+1] == "R":
        ret += 1
print(ret)

Submission status: Accepted

Solution code:

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

t=[]
for i in range(1,n):
	if s[i]!=s[i-1]:
		t.append(i)
x=[]
for y in s:
	if y=="L":
		x.append(0)
	else:
		x.append(1)

if len(t)<=2*k:
	print(n-1)
	import sys
	sys.exit()

y=[0 for _ in range(n)]
for i in range(k):
	y[t[i]]+=1
	y[t[-i-1]]-=1
for i in range(1,n):
	y[i]=(y[i]+y[i-1])%2
#print(x)
#print(y)
z=[(x[i]+y[i])%2 for i in range(n)]
#print(z)

res=0
for i in range(1,n):
	if z[i]==0 and z[i-1]==0:
		res+=1
for i in range(n-1):
	if z[i]==1 and z[i+1]==1:
		res+=1
print(res)

Submission status: Accepted

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

#print(s)

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

if(part%2 == 1):
    if(k>= (part-1)//2):
        print(n-1)
    else:
        print(n-1 - ((part-1)//2 - k)*2)
else:
    if(k >= part//2):
        print(n-1)
    else:
        print(n - (part//2 - k)*2)

Submission status: Accepted

Solution code:
import sys
import collections
import copy
import math
def input(): return sys.stdin.readline().strip()
N ,K= map(int,input().split())
S = input()
cuts = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        cuts += 1
print(min(N-1,N-1-cuts+2*K))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
X=[1]
for i in range(1,N):
    if S[i]!=S[i-1]:
        X.append(1)
    else:
        X[-1]+=1
M=len(X)
T=M-2*K
if T<=0:
    T=1
print(N-T)

Submission status: Accepted

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

before=s[0]

tenkan=0
fortune=0

for i in range(n):
    if s[i]!=before:
        tenkan+=1
    elif i!=0:
        fortune+=1
    before=s[i]

#print(tenkan, fortune)

while k>0:
    if tenkan>=2:
        tenkan-=2
        fortune+=2
        k-=1
    elif tenkan==1:
        tenkan-=1
        fortune+=1
        k-=1
    else:
        k-=1

print(fortune)

Submission status: Accepted

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

Submission status: Accepted

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

tmp = 0
for i in range(len(s)):
    if i == 0:
        if s[i] == 'R' and s[i+1] == 'R':
            tmp += 1
    elif i == len(s) - 1:
        if s[i] == 'L' and s[i- 1] == 'L':
            tmp += 1
    else:
        if s[i] == 'R' and s[i+1] == 'R':
            tmp += 1
        elif s[i] == 'L' and s[i- 1] == 'L':
            tmp += 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

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

S = np.array(list(input()), dtype='U1')

x = np.count_nonzero(S[1:] == S[:-1])

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = [1 if s == 'L' else 0 for s in input().strip()] + [-1]

pre = None
ans = 0
cnt = -2
for s in S:
    if s == pre:
        ans += 1
    else:
        cnt += 1
    pre = s

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

Submission status: Accepted

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

num = Ss.count('LR') + Ss.count('RL') + 1

ans = N - max(1, num-2*K)
print(ans)

Submission status: Accepted

Solution code:

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

s = input()

S = list(s)

num = 0
for i in range(N-1):

    if S[i] == S[i+1]:
        num += 1

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

Submission status: Accepted

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

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,k = mi()
    muki = input()
    muki = 'r'+muki+'l'
    ans = 0
    for i in range(1,n+1):
        if muki[i] == 'L':
            if muki[i-1] == 'L':
                ans+=1
        if muki[i] == 'R':
            if muki[i+1] == 'R':
                ans+=1
    ans+=2*k

    ans = min(ans,n-1)
    print(ans)


main()

Submission status: Accepted

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

a=0

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

ans=min((a+2*k),n-1)
print(ans)

Submission status: Accepted

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

ans = 0
rev = 0
for i in range(1, n):
  if s[i-1]==s[i]:
    ans += 1
  else:
    rev += 1
ans += min(k*2, rev)
print(ans)

Submission status: Accepted

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

dif = 0
for i in range(n-1):
    if s[i] != s[i+1]:
        dif += 1
#print(dif)
dif = max(dif - 2*k, 0)
print(n - dif - 1)

Submission status: Accepted

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

s_prev = '#'
happy = 0
for i in range(N):
    s = S[i]
    if s == s_prev:
        happy += 1
    s_prev = s

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=[int(i) for i in input().split()]
s=input()
ans=0
for i,j in zip(s[:-1],s[1:]):
  if i!=j:
    ans+=1
print(n-1-max(ans-2*k,0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
if k>=n:print(n-1);exit()
hpp=0
for i in range(n-1):
    if s[i]==s[i+1]:hpp+=1
print(min(n-1,hpp+k*2))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num , k = map(int, input().split())
    data = list(input())

    ans = 0
    for i in range(num - 1):
        if data[i] == data[i + 1]:
            ans += 1
    ans = min(num - 1, ans + 2 * k)
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
prev = None
count = 0
for x in s:
  if x == prev:
    count += 1
  prev = x
print(min(count + k * 2, n - 1))

Submission status: Accepted

Solution code:

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

pt = 0
sak = 0

mae = s[0]
for i in range(1,n):
    if s[i] == mae:
        pt += 1
    else:
        sak += 1
    mae = s[i]

print(pt + min(sak, k * 2))

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0

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

ans = min(n-1,ans + 2*k)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
S = input()
count=0
for i in range(N-1):
    if S[i]==S[i+1]:
        count+=1

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()
if n==1:
    print(0)
    exit()
cnt=1
prev=S[0]
for s in S[1:]:
    if s!=prev:
        cnt+=1
    prev=s
if cnt-2*k<1:
    print(n-1)
else:
    print(n-cnt+2*k)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    s = input()
    
    islands = 0
    for i in range(1, n):
        if s[i] != s[i - 1]:
            islands += 1
    
    islands = max(0, islands - 2 * k)
    
    print(n - 1 - islands)
    
    return 0

main()

Submission status: Accepted

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

h = 0
for a,b in zip(S,S[1:]):
    if a==b:
        h += 1
h += 2*K
print(min(N-1, h))