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
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, S):
    sachi = 0
    L_cluster, R_cluster = (0, 1) if S[0] == 'R' else (1, 0)
    for i in range(N):
        if S[i] == 'R' and i != N - 1 and S[i + 1] == 'R':
            sachi += 1
        if S[i] == 'L' and i != 0 and S[i - 1] == 'L':
            sachi += 1
        if i > 0 and S[i] != S[i - 1]:
            if S[i] == 'R':
                R_cluster += 1
            else:
                L_cluster += 1

    ans = 0
    reverse_cluster = min(L_cluster, R_cluster)
    if K >= reverse_cluster:
        ans = N - 1
    else:
        ans = sachi + K * 2

    print(ans)


if __name__ == '__main__':
    # N = int(input())
    N, K = map(int, input().split())
    S = input()
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(N, K, S)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
let=input()
can=0
for i in range(N-1):
   if let[i]!=let[i+1]:
      can+=1
if can<=K*2:
   print(N-1)
else:
   can-=K*2
   print(N-can-1)

Submission status: Accepted

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

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

ans = n - 2*rl - end

if end == 0:
    if k >= rl:
        ans += 2*rl
        ans -= 1
    else:
        ans += 2*k
elif end == 1:
    if k >= rl:
        ans += 2*rl
    else:
        ans += 2*k
elif end == 2:
    if k == rl:
        ans += 2*rl
    elif k >= rl+1:
        ans += 2*rl
        ans += 1
    else:
        ans += 2*k
print(ans)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

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

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

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    S=input()
    
    ans=0
    now="A"
    for i in range(N):
        if S[i]==now:
            ans+=1
        now=S[i]
    
    ans=(min(N-1,ans+K*2))
    print(ans)
        

main()

Submission status: Accepted

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N, K = MI()
    original = input()
    num_happy = 0

    for i in range(N - 1):
        if original[i] == original[i+1]:
            num_happy += 1

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


main()

Submission status: Accepted

Solution code:
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, len(sa)), 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: Accepted

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

A=0
for i in range(1,N+1):
    if S[i]=="L":
        A+=(S[i-1]=="L")
    elif S[i]=="R":
        A+=(S[i+1]=="R")

for i in range(K):
    A=min(N-1,A+2)

print(A)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(input())
count=0
for i in range(n):
    if a[i]=="L" and i-1>=0 and a[i-1]=="L":
        count+=1
    elif a[i]=="R" and i+1<=n-1 and a[i+1]=="R":
        count+=1
print(min(n-1,count+k*2))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
s = input()
v = 0
l = [[s[0],1]]
for c in s[1:]:
    if l[-1][0]!=c:
        l.append([c,1])
    else:
        l[-1][1] += 1
vs = []
if len(l)==1:
    ans = n-1
else:
    num = 0
    for i in range(n):
        if (i==0 and s[i]=="L") or (i==n-1 and s[i]=="R") or (0<=i<=n-2 and s[i]=="R" and s[i+1]=="L") or (1<=i and s[i]=="L" and s[i-1]=="R"):
            num += 1
    vals = []
    for i in range(len(l)):
        if l[i][0]=="L":
            if i in (0, len(l)-1):
                vals.append(1)
            else:
                vals.append(2)
    vals.sort()
    ans = n - (num - sum(vals[-k:]))
    
    vals = []
    for i in range(len(l)):
        if l[i][0]=="R":
            if i in (0, len(l)-1):
                vals.append(1)
            else:
                vals.append(2)
    vals.sort()
    ans = max(ans, n - (num - sum(vals[-k:])))
    
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
pre = s[0]
rs = 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:
        rs = rs + first
        pre = i
    elif i == first and pre == second:
        k -= 1
        rs = rs + i
        pre = i
    elif k == 0:
        rs = rs + i
    elif i == first and pre == first:
        rs = rs + i

pre = "0"
ans = 0

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

print(ans)

Submission status: Accepted

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

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

S = input()

cnt = 0
b = S[0]

for i in range(1,N):
  if b != S[i]:
    cnt += 1
  b = S[i]
  
if cnt % 2 == 1:
  if K > cnt//2:
    print(N-1)
  else:
    print(N-2*(cnt//2+1)+2*K)
else:
  if K >= cnt//2:
    print(N-1)
  else:
    print(N-cnt+2*K-1)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

if S[0] == "L":
    ans += 1
if S[N-1] == "R":
    ans += 1

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

Submission status: Accepted

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

ans = []
c = 1
# RL圧縮
for i in range(1,n):
    if S[i-1] == S[i]:
        c += 1
    else:
        ans.append(c)
        c = 1
ans.append(c)
# ansの個数は1個毎に減っていく
if len(ans) // 2  <= k:
    print(n-1)
else:
    d = len(ans) - 2*k
    print(n-d)

Submission status: Accepted

Solution code:
(str_len,cng_cnt) = input().split(" ")
str_input = list(input())

str_len= int(str_len)
cng_cnt= int(cng_cnt)
tmp1=""
cnt=0
cnt2=0
for st in str_input:
    if(tmp1 == st ):
      cnt = cnt+1
    else:
      cnt2= cnt2 + 1
      
    tmp1=st

if (cng_cnt < cnt2-1 ):
	c_up = cng_cnt * 2 
else:
	c_up= (cnt2 * 2) + (cng_cnt - cnt2)
ans =cnt + c_up

if(ans >= str_len):
  ans =str_len-1

print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    '''
    RL...LL 0
    RL...RR 0
    RL...RL 0

    RL...LR +2
    LR...RL +2

    RL      +1

    13 3
    LRRLRLRRLRLLR
    '''
    N, K = read_ints()
    S = input()
    score = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            score += 1
    return min(score+2*K, N-1)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
s=list(input())
ans=[]
c=1
for i in range(1,n):
    if s[i]==s[i-1]:
        c+=1
    else:
        ans.append(c)
        c=1
ans.append(c)
if len(ans)//2<=k:
    print(n-1)
else:
    print(n-len(ans)+2*k)

Submission status: Accepted

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)

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

for i in range(len(ll)-1):
    if i<len(rr) and 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: Accepted

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

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(n-1,n-1-cnt+2*k))

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 = n - 1 - max(a - 2 * k, 0)
print(ans)

Submission status: Accepted

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

rights = []
lefts = []

for i in range(N):
    if i == 0:
        if S[i] == "L":
            now = "L"
            start = i
        else:
            now = "R"
            start = i
    else:
        if S[i] != now:
            end = i
            if now == "R":
                rights.append((start, end))
            else:
                lefts.append((start, end))
            start = i
            now = S[i]
            if i == N-1:
                if now == "R":
                    rights.append((i, i+1))
                else:
                    lefts.append((i, i+1))

n_inner_left = 0
n_inner_right = 0
for left in lefts:
    if (0 not in left) and (N not in left):
        n_inner_left += 1
for right in rights:
    if (0 not in right) and (N not in right):
        n_inner_right += 1
# unhappy
total = 0
if S[0] == "L":
    total += 1
if S[N-1] == "R":
    total += 1
for i in range(N-1):
    if S[i] == "R" and S[i+1] == "L":
        total += 2

rest = K
if n_inner_left > n_inner_right:
    reduce_2 = min(K, n_inner_left)
    total -= 2*reduce_2
    rest -= reduce_2
    if S[0] == "L" and rest > 0:
        total -= 1
elif n_inner_left < n_inner_right:
    reduce_2 = min(K, n_inner_right)
    total -= 2*reduce_2
    rest -= reduce_2
    if S[N-1] == "R" and rest > 0:
        total -= 1
else:
    reduce_2 = min(K, n_inner_left)
    total -= 2*reduce_2
    rest -= reduce_2
    if rest > 0:
        if S[0] == "L" and S[N-1] == "R":
            total -= 1
        if S[0] == "R" and S[N-1] == "L":
            total -= 1


print(N-total)

Submission status: Accepted

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

Submission status: Accepted

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

from_start = 0
RtoL = 0
LtoR = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        from_start += 1
    elif s[i] == 'R' and s[i+1] == 'L':
        RtoL += 1
    elif s[i] == 'L' and s[i+1] == 'R':
        LtoR += 1
add = 0
while (RtoL or LtoR) and k:
    k-=1
    if RtoL and LtoR:
        add += 2
        RtoL -= 1
        LtoR -= 1
    elif RtoL:
        add += 1
        RtoL -= 1
    elif LtoR:
        add += 1
        LtoR -= 1
print(from_start+add)

Submission status: Accepted

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

Submission status: Accepted

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

s_=''
S_=[]

if len(set(S))==1:
    ans = len(S)-1
    
else:
    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: Accepted

Solution code:

# find the cluster of LLLLL....... and RRRRR....
# Reversing these cluster increases happiness by 2
# either the leftmost or the rightmost will remain unhappy forever can't help :(
def main():
	n , k = map(int, input().split())
	s = input()
	uh=0
	for i in range(0 , len(s)-1):
		if s[i]!=s[i+1]:
			uh=uh+1
	hp = n-1 - max(uh-2*k , 0)
	print(hp)


if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:


def main():
	n , k = map(int, input().split())
	s = input()
	uh=0
	for i in range(0 , len(s)-1):
		if s[i]!=s[i+1]:
			uh=uh+1
	hp = n-1 - max(uh-2*k , 0)
	print(hp)


if __name__=="__main__":
	main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

t = [s[0]]

for i in range(1, n):
    if s[i-1] != s[i]:
        t.append(s[i])

#print(t)

a = 0

if len(t) <= 2 * k:
    a = n-1
else:
    a = (n-1) - (len(t) - 1 - 2 * k)

print(a)

Submission status: Accepted

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)

Submission status: Accepted

Solution code:

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    n, k = map(int, input().split())
    s = input()
    n = len(s)
    ans = 0
    for i in range(n-1):
        if s[i+1] == s[i]:
            ans += 1
    while ans < n-1 and k > 0:
        if n-1-ans > 1:
            ans += 2
        elif n-1-ans == 1:
            ans+=1
        k -=1
    print(ans)
    
    

if __name__ == '__main__':
    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 = N - 1 - max(0, a - (2 * K))
print(ans)

Submission status: Accepted

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

ln, rn = 0, 0

i = 0
while i < n:
    if s[i] == 'R':
        while i < n and s[i] == 'R':
            i += 1
        rn += 1
    if i < n and s[i] == 'L':
        while i < n and s[i] == 'L':
            i += 1
        ln += 1
m = min(ln, rn)
if m > k:
    if ln == rn:
        print(n - 2 * (m - k))
    else:
        print(n - 2 * (m - k) - 1)
else:
    print(n - 1)

Submission status: Accepted

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

unhappiness = 0
m1, m2 = 0, 0

if s[0] == 'L':
    unhappiness += 1
if s[-1] == 'R':
    unhappiness += 1
i = 0
while i < n and s[i] == 'L':
    i += 1
while i < n:
    h = i
    while i < n and s[i] == 'R':
        i += 1
    if i == n:
        break
    while i < n and s[i] == 'L':
        i += 1
    if h != 0 and i != n:
        m2 += 1
    elif h != 0 or i != n:
        m1 += 1
    unhappiness += 2

if  k <= m2:
    unhappiness -= 2 * k
else:
    unhappiness -= 2 * m2
    k -= m2
    if m1 == 2:
        k -= 1
        unhappiness -= 2
    if k > 0:
        unhappiness = 1
print(n-unhappiness)

Submission status: Accepted

Solution code:
import copy

n, k =  map(int,input().split())
s = ['R'] + list(input()) + ['L']

cnt = 0
for i in range(1,n+1):
    if s[i] == 'L' and s[i-1] == 'L':
        cnt += 1
    if s[i] == 'R' and s[i+1] == 'R':
        cnt += 1
# print(cnt)
while k > 0 and cnt < n-1:
    if n- 1 - cnt > 1:
        cnt += 2
    elif n- 1 - cnt > 0:
        cnt += 1
    k -= 1
print(cnt)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

ori_num=0
turn_num=0
for i in range(N):
    if i>0:
        if S[i-1] =='L' and S[i] =='L':
            ori_num += 1
        if S[i-1] != S[i]:
            turn_num +=1
        
    if i<N-1:
        if S[i] =='R' and S[i+1] =='R':
            ori_num += 1

if turn_num >=2*K:
    ori_num += 2*K
else:
    num = turn_num//2
    num2 = turn_num%2
    ori_num += 2*num+num2
    
print(ori_num)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
target = input('')
target = list(target)
ans = 0
p = 0
for i in range(1, n):
    if target[i-1] != target[i]:
        p += 1
    else:
        ans += 1

print(ans+min(p, k*2))

Submission status: Accepted

Solution code:
def solve(a,k):
    curr_char = a[0]
    curr_len = 0
    segs = 1
    for x in a:
        if x==curr_char:
            curr_len += 1
        else:
            segs += 1
            curr_len = 1
            curr_char = x
    return len(a)-max(1,segs-2*k)
n,k = map(int,input().split())
print(solve([1 if c=='L' else 0 for c in input()],k))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 最初の幸福度
    h = 0
    for i in range(N - 1):
        if S[i] == S[i+1]:
            h += 1

    # YX...XYに対して操作をすると幸福人数を2増やせる
    # 端X...XYに対して操作をすると幸福人数を1増やせる
    cnt = 0
    for i in range(N - 1):
        if S[i] != S[i+1]:
            cnt += 1

    if cnt >= 2 * K:
        h += 2 * K
    else:
        h = N - 1 

    print(h)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# 「操作を最大 K 回まで行うことができる」という問題設定は、アルゴリズム的にできることがとても限られてくる
# ・1回操作するごとに、何らかの値が規則的に変化していく
# ・なんらかの意味で Greedy に、順にやっていくとよい
# とにかく、操作の意味をわかりやすく言い換える
# 文字列S(長さN)のスコアは、「文字と文字との間の隙間(N-1個)」のうちLとRが隣接しているもの(a個とする)を除いた、N−1−a
# 一回の反転操作で、LとRの変わり目を2箇所減らすことができる
# よって、求める最大値は N−1−max(a−2K,0)
N, K = map(int, input().split())
S = input()

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

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

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
s = str(input())
ans = 0
for i in range(1,len(s)):
  if s[i] == s[i-1]:
    ans += 1

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

print(ans)

Submission status: Accepted

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

cnt = 0
s0 = "$"
for s in S:
    if s != s0:
        cnt += 1
    s0 = s

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

Submission status: Accepted

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

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

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

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:

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

cnt = S.count("RL")
edge = int(S[0] == "L") + int(S[-1] == "R")

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

Submission status: Accepted

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
print(min(happy+k*2, n-1))

Submission status: Accepted

Solution code:
import sys
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()

def main():
    n,k=map(int, input().split())
    S=list(input())
    p=len(list(groupby(S)))-2*k 
    pp=max(p,1)
    print(n-pp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
lr = 0
rl = 0
ans = 0
for i in range(n-1):
    if s[i]=='L' and s[i+1]=='R':
        lr += 1
    elif s[i]=='R' and s[i+1]=='L':
        rl += 1
    else:
        ans += 1

if lr >= k and rl >= k:
    ans += 2*k
elif lr == rl:
    ans += 2*lr
else:
    num = max(lr, rl)
    ans += 2*num-1

print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
s = sr()
rl = 0
default = 0
ret = 0
for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L':
        rl += 1
    elif s[i] == s[i+1]:
        default += 1
if rl == 0:
    print(n-1)
else:
    ret = 0
    if s[0] != s[n-1]:
        ret = 1
        if s[n-1] == 'L':
            rl-=1
    ans = default
    ans += 2*min(rl, k)
    if k-rl > 0:
        ans+=ret
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
cnt = 0
tmp = s[0]
t = 0
for i in range(1, n):
    if tmp == s[i]:
        continue
    else:
        cnt += 1
        tmp = s[i]
c = 0
for i in range(1, n):
    if s[i] == s[i-1]:
        c += 1
if cnt <= 2*k:
    print(n-1)
else:
    print(c + 2*k)

Submission status: Accepted

Solution code:
#coding: utf-8

N, K = (int(i) for i in input().split()) 
S = input()

while "LL" in S:
    S = S.replace("LL", "L")

while "RR" in S:
    S = S.replace("RR", "R")

sad = N - len(S)
sad += K * 2

sad = min(N-1, sad)
print(sad)

Submission status: Accepted

Solution code:
def count(s):
	c=0
	
	for i in range(len(s)-1):
		if s[i+1] == s[i]:
			c += 1
	return c
	
n, k = map(int, input().split())
s = input()
a = [str(c) for c in s]
cmax = n-1
p = count(a)
while 1:
  if p == cmax:
    break
  elif p == cmax +1:
    p -=1
    break
  elif k > 0:
    p += 2
    k -= 1
  else:
    break
		
print(p)

Submission status: Accepted

Solution code:
import heapq
t = 1
def max(a,b):
	if a > b:
		return a
	return b
def min(a,b):
	if a < b:
		return a
	return b

while t > 0:
	t -= 1
	n,k = map(int,input().split())
	# n = int(input())
	# a = list(map(int,input().strip().split()))[0:n]
	# b = list(map(int,input().strip().split()))[0:n]
	# c = list(map(int,input().strip().split()))[0:n-1]
	s = input()
	i = 0
	ans = 0
	c = 0
	d = 0
	while(i < n):
		j = i
		# c += 1
		if s[i] == 'R':
			c += 1
		else:
			d += 1
		while j+1 < n and s[j+1] == s[i]:
			j += 1
		l = j-i+1
		ans += (l-1)
		i = j+1
	c = min(c,d)
	# print()
	if s[0] == s[n-1]:
		if k < c:
			# print("a")
			ans += 2*k
		else:
			# print("b")
			ans += 2*(c)
	else:
		if k < c:
			# print("a")
			ans += 2*k
		else:
			ans += 2*(c-1)
			ans += 1
		# ans += 1
		# ans += 1
	print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
s = input()
l = s.count('L')

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

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

Submission status: Accepted

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

s=list(input())

now_happy_count = 0

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

index = 0

reverse_candidate = []

while index < n:
    if s[index] != s[0]:
        start = index
        while index < n and s[index] != s[0]:
            index += 1
        end = index - 1
        reverse_candidate.append([start, end])
    else:
        index += 1

if len(reverse_candidate) <= k:
    print(n-1)
else:
    print(now_happy_count+2*k)

Submission status: Accepted

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

Submission status: Accepted

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

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