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 = input()
S = list(S)

cnt = 0
s = S[0]
flag = False
for i in range(n):
    if flag and S[i] == s:
        cnt += 1
        flag = False
    if S[i] != s:
        S[i] = s
        flag = True
    if cnt == k:
        break

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

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
tmp=0
m=0
omake=0
for i in range(n-1):
    if s[i]!=s[i+1]:
        tmp+=1
        if tmp%2==0:
            m+=1
        elif i==n-2:
            omake+=1
    elif tmp>0 and i==n-2 and tmp%2==1:
        omake+=1

if m<k:
    print(ans+2*min(m,k)+omake)
else:
    print(ans+2*min(m,k))

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
S = input()
Now = S[0]
switch = 0
happiness = 0
for i in range(N-1):
  if(S[i+1] == Now):
    happiness += 1
  if(S[i+1] != Now):
    Now = S[i+1]
    switch += 1
number = 0
while((switch > 1) and (number < K)):
  number += 1
  happiness += 2
  switch -= 2
if((switch == 1) and (number < K)):
  happiness += 1
print(happiness)

Submission status: Accepted

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

base = 0
odd = 0

pre_char = 'N'
for index, char in enumerate(s):
    if index > 0:
        if pre_char == char:
            base += 1
        else:
            odd += 1
    pre_char = char

#if k >= odd:
#    output = len(s) - 1
#elif odd - k == 1:
#    output = base + 2 * (k - 1) + 1
#else:
#    output = base + 2 * k

output = base + 2 * k
if output > len(s) - 1:
    output = len(s) - 1

print(output)

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

Submission status: Accepted

Solution code:
N , K  = map(int,input().split())
S = [0 if s == "L" else 1 for s in input()]
def main():
    rep = 1
    pre = S[0]
    for s in S[1:]:
        if s != pre:
            rep += 1
        pre = s
    print(N - (rep - 2*K) if rep - 2*K > 0 else N - 1)
    return
main()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
s=list(input())
ct=0
for i in range(n-1):
  if s[i]=='R' and s[i+1]=='L':ct+=1
if ct<=k-1:
  print(n-1)
  sys.exit()
ans=n-ct*2
ans+=2*k
if s[0]=='L':
  ans-=1
if s[n-1]=='R':
  ans-=1
print(ans)

Submission status: Accepted

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

def search(s):
    ret = 0
    for i in range(len(s)):
        if s[i] == 'R' and i != n - 1:
            if s[i + 1] == 'R':
                ret += 1
        if s[i] == 'L' and i != 0:
            if s[i - 1] == 'L':
                ret += 1
    return ret

ans = search(s)
print(min(ans + 2 * k, len(s) - 1))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, k = rrd()

s = list(map(str, rd().strip()))

cnt = 0
pre = 'i'
for x in s:
    if x != pre:
        cnt += 1
    pre = x

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

Submission status: Accepted

Solution code:
import math
import copy

#n = int(input())
n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#b = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

kotae = 0

for i in range(n) :
    if (i == 0) :
        if (n == 1) :
            break
        if (s[i] == "R" and s[i+1] =="R") :
            kotae += 1
    elif (i == n-1) :
        if(s[i] == "L" and s[i-1] == "L") :
            kotae += 1
    else :
        if (s[i] == "L" and s[i - 1] == "L") :
            kotae += 1
        elif (s[i] == "R" and s[i+1] == "R") :
            kotae += 1

j = 0



for i in range(1, n) :
    if (n == 1) :
        break
    if (s[i] != s[i-1]) :
        j += 1

kotae += min(2*k,j)


print(kotae)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
s = input()
chg = 0
for i in range(n-1):
    if s[i] != s[i+1]:
        chg += 1
if chg <= 2*k:
    print(n-1)
else:
    chg -= 2*k
    print(n-1-chg)

Submission status: Accepted

Solution code:
#Dギャンブル

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

for i in range(n):
    if s[i] == "L" and i == 0:
        kfk.append(0)
    elif s[i] == "L" and i != 0:
        if s[i-1] == "L":
            kfk.append(1)
        else:
            kfk.append(0)
    elif s[i] == "R" and i == (n-1):
        kfk.append(0)
    elif s[i] == "R" and i != (n-1):
        if s[i+1] == "R":
            kfk.append(1)
        else:
            kfk.append(0)

ans = sum(kfk) + (2 * k)
if ans < (n-1):
    print(ans)
else:
    print(n-1)

Submission status: Accepted

Solution code:
N , K = [int(i) for i in input().split()]
S = input()

S = 'R' + S + 'L'

a = 0

for i in range(N+1):
    if S[i] == 'R' and S[i+1] == 'L':
        a += 2

if S[1] == 'L':
    a -= 1

if S[-2] == 'R':
    a -= 1

ans = N - a + (2*K)

if ans > N-1:
    ans = N-1
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def score(S):
    S0 = [' '] + S + [' ']
    score = 0
    s = [0]*len(S0)
    for i in range(1, len(S)+1):
        c = S0[i]
        if c == 'L':
            s[i] += 1 if S0[i-1] == 'L' else 0
        else:
            s[i] += 1 if S0[i+1] == 'R' else 0
    return sum(s)

def main2():
    N, K = map(int, input().split())
    S = list(input().strip())
    m = score(S)
    
    print(min(m + 2 * K, N-1))

def main():
    N, K = map(int, input().split())
    S = list(input().strip())
    print(S, score(S), "initial")
    m = score(S)
    for ps in permutations([(i, j) for i in range(N) for j in range(i, N)], K):
        S_ = list(S)
        for p in ps:
            apply(S_, p)
        s = score(S_) 
        if m < s:
            mp = ps
            m = s
    S_ = list(S)
    for p in mp:
        apply(S_, p)
        print(S_, score(S_), p)
    print(m, mp)

def apply(S, lr):
    l, r = lr
    for i in range(r-l+1):
        if l+i > r-i:
            break
        S[l+i], S[r-i] = S[r-i], S[l+i]
        S[l+i] = 'R' if S[l+i] == 'L' else 'L'
        if l+i != r-i:
            S[r-i] = 'R' if S[r-i] == 'L' else 'L'

if 1==0:
    S = list("LLLLL")
    apply(S, (0, 4))
    print(S)

main2()

Submission status: Accepted

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

s = s+"a" #拡張して扱いやすくする

lst = [i for i in s]

ans = 0
memo1 = 0
memo2 = 0
for i in range(n):
    if lst[i] == lst[i+1]:
        ans += 1
    elif lst[i] == "L" and lst[i+1] == "R":
        memo1 += 1
    elif lst[i] == "R" and lst[i+1] == "L":
        memo2 += 1
        
ans += 2*min(k,memo1,memo2)
num = min(k,memo1,memo2)

jdg = False
jdg2 = False

if memo1 >= num+1 and lst[n-1] == "R" and num < k:
    ans += 1
    jdg = True
if jdg:
    if memo2 >= num+2 and lst[0] == "L" and num < k+1:
        ans += 1
        jdg2 = True
else:
    if memo2 >= num+1 and lst[0] == "L" and num < k:
        ans += 1
        jdg2 = True
        
if not(jdg):
    if memo2 >= num+1 and lst[n-1] == "L" and num < k:
        ans += 1
        jdg = True
    if jdg:
        if memo1 >= num+2 and lst[0] == "R" and num < k+1:
            ans += 1
            jdg2 = True
    else:
        if memo1 >= num+1 and lst[0] == "R" and num < k:
            ans += 1
            jdg2 = True
    
elif not(jdg2):
    if memo2 >= num+1 and lst[n-1] == "L" and num < k:
        ans += 1
        jdg = True
    if jdg:
        if memo1 >= num+2 and lst[0] == "R" and num < k+1:
            ans += 1
            jdg2 = True
    else:
        if memo1 >= num+1 and lst[0] == "R" and num < k:
            ans += 1
            jdg2 = True
    
    

print(ans)

Submission status: Accepted

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

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

happiness = 0
unhappiness = 0

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

if S[0] == 'R':
    if S[0] == S[1]:
        happiness += 1
    else:
        unhappiness += 1
else:
    unhappiness += 1
# print(S[0], happiness, unhappiness)

for i in range(1, N - 1):
    c = S[i]
    if c == 'R':
        nex = S[i + 1]
    elif c == 'L':
        nex = S[i - 1]

    if c == nex:
        happiness += 1
    else:
        unhappiness += 1
    # print(c, happiness, unhappiness)

if S[-1] == 'L':
    if S[-1] == S[-2]:
        happiness += 1
    else:
        unhappiness += 1
else:
    unhappiness += 1
# print(S[-1], happiness, unhappiness)

# print(happiness, unhappiness, K)

moves = min(unhappiness // 2, K)
plus_happiness = unhappiness % 2 if K - moves > 0 else 0
ans = 2 * moves + happiness + plus_happiness
# print(moves, happiness, plus_happiness)
print(min(ans, N-1))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
if len(s) == 1:
    print(0)
    exit()

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

if c == 1:
    print(n-1)
    exit()


t = -1
left = s[0]
q = -1
for i in range(1,n):
    if s[i] != left:
        t += 1
        left = s[i]
    if t == 1 and k > 0:
        k -= 1
        ans += 2
        t = -1

if t == 0 and k > 0:
    ans += 1
print(ans)

Submission status: Accepted

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

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

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

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

    if t%2 == 1 and t//2 < K:
        x += 1

    print(x)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

LR = S.count("LR")
RL = S.count("RL")
RRLL = N-1-LR-RL

if min(LR,RL) != 0: 
    if K <= min(LR,RL):
        print(RRLL+K*2)       
    if K > min(LR,RL):
        if min(LR,RL) != max(LR,RL):
            print(RRLL+min(LR,RL)*2+1)
        if min(LR,RL) == max(LR,RL):
            print(RRLL+min(LR,RL)*2)
if min (LR,RL) == 0:
    if max(LR,RL) !=0:
        print(RRLL+1)
    if max(LR,RL) ==0:
        print(RRLL)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
switch = 0
ans = 0
for i in range(1,len(S)):
    if S[i] != S[i-1]:
        switch += 1
    else:
        ans += 1
for i in range(K):
    if switch == 0:
        break
    elif switch == 1:
        switch -= 1
        ans += 1
    else:
        switch -= 2
        ans += 2
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
n,k=map(int,input().split())
s=input()
buf=s[0]
a = deque([]) 
count=0
ans=0
for i in range(n):
    if buf==s[i]:
        count+=1
    else:
        a.append(count)
        count=1
        buf=s[i]
    if i==n-1:
        a.append(count)
l=len(a)
c=0
for i in range(l):
    ans+=a[i]-1
for i in range(l//2):
    if c==k:
        break
    if 2*i+1!=l-1:
        ans+=2
        c+=1

if c<k:
    ans+=k-c
    ans=min(n-1,ans)
print(ans)

Submission status: Accepted

Solution code:
def mapping(string):
    return 1 if string == "L" else -1


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

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

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

Submission status: Accepted

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

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

nr = 0
nl = 0
for i in range(N):
    if i == 0:
        if S[i] == 'R':
            nr += 1
        elif S[i] == 'L':
            nl += 1
    else:
        if S[i] == 'R' and S[i-1] == 'L':
            nr += 1
        elif S[i] == 'L' and S[i-1] == 'R':
            nl += 1

#print(nr)
#print(nl)

rcheck = 0
lcheck = 0
if S[0] == 'R':
    rcheck += 1
else:
    lcheck += 1
if S[-1] == 'R':
    rcheck += 1
else:
    lcheck += 1

ans = saisyo

#rの時
if nr - K >= 2:
    ans += 2*K
elif nr - K == 1:
    if rcheck == 0:
        ans += 2*K
    elif rcheck >= 1:
        ans += 2*K - 1
elif nr - K == 0:
    if rcheck == 0:
        ans += 2*K
    elif rcheck >= 1:
        ans += 2*K - 1
    elif rcheck == 2:
        ans += 2*K - 2
else:
    ans += 2*nr - rcheck

rans = ans 
ans = saisyo

#lの時
if nl - K >= 2:
    ans += 2*K
elif nl - K == 1:
    if lcheck == 0:
        ans += 2*K
    elif lcheck >= 1:
        ans += 2*K 
    elif lcheck >= 1:
        ans += 2*K - 1
elif nl - K == 0:
    if lcheck == 0:
        ans += 2*K
    elif lcheck >= 1:
        ans += 2*K - 1
    elif lcheck == 2:
        ans += 2*K - 2
else:
    ans += 2*nl - lcheck

lans = ans

ans = max(rans, lans)
print(ans)

Submission status: Accepted

Solution code:
a = list(map(int,input().split()))
s = list(input())
kou = 0
LR = 0
RL = 0
for (i,j) in zip(s[:-1],s[1:]):
    if i == j:
        kou += 1
    elif i == 'L' and j == 'R':
        LR += 1
    else:
        RL += 1
kou += min(2*a[1],LR+RL)
print(kou)

Submission status: Accepted

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

c = []
c_ap = c.append
cnt = 0

result = 0

for i in range(N - 1):
    if S[i] == S[i + 1]:
        result += 1
    if S[i] == "R":
        if S[i + 1] == "L":
            c_ap(cnt + 1)
            cnt = 0
        else:
            cnt += 1
            
            
if len(c) == 0 and "R" in S:
    result += 1
if len(c) >= K:
    result += K * 2
else:
    result = N - 1

print(result)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, K = map(int, input().split())
    S = str(input())
    count = 0
    
    LR = 0
    RL = 0
    
    for i in range(N-1):
        if S[i] == 'R' and S[i+1] == 'R':
            count += 1
        elif S[i+1] == 'L' and S[i] == 'L':
            count += 1
    
    for i in range(N-1):
        if S[i] == 'L' and S[i+1] == 'R': #Lで不幸せな人を見つけた
            LR += 1  
                    
        elif S[i] == 'R' and S[i+1] == 'L': #Rで不幸せな人を見つけた
            RL += 1
    
    for i in range(K):
        if LR > 0 and RL > 0:
            LR -= 1
            RL -= 1
            count += 2
        else:
            if LR > 0 or RL > 0:
                count += 1
                break
            
    print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    f_d()

Submission status: Accepted

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

count = []
pre = S[0]
c = 1
for t in S[1:] :
    if t == pre :
        c += 1
    else :
        count.append(c)
        pre = t
        c = 1
        
ret = sum(count)-len(count)
if K < len(count) // 2 :
    ret += 2 * K
else :
    ret = N - 1
print(ret)

Submission status: Accepted

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

length = len(S)
point=0

tmp = S[0]
for i in range(1, len(S)):
    if tmp==S[i]:
        length-=1
        point+=1
    tmp = S[i]

capacity = length-1
point += min(capacity, K*2)

# print(length)
print(point)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
from collections import *
from bisect import *
from copy import deepcopy
mod = 10**9+7

N, K = map(int, input().split())
T = [0 if x == 'L' else 1 for x in input()]
f = 0
cnt = 1
for i in range(N-1):
    if T[i] != T[i+1]:
        cnt += 1
if cnt//2 <= K:
    f = 1
ans1 = ans2 = N-cnt
# print(ans1, ans2, cnt)
S = [x for x in T]
l, r, k = 0, N-1, 0
while l < N and S[l] == 1:
    l += 1
# ans1 += l
while l < N-1 and S[l+1] == 0:
    l += 1
while 0 <= r and S[r] == 1:
    r -= 1
# ans1 += N-r-2
while 0 < r and S[r-1] == 0:
    r -= 1
# print(ans1)
while l < r and k < K:
    k += 1
    ans1 += 2
    l += 1
    r -= 1
    while l < r and S[l] == S[l+1]:
        l += 1
    while l < r and S[r-1] == S[r]:
        r -= 1

S = [x for x in T]
l, r, k = 0, N-1, 0
while l < N and S[l] == 0:
    l += 1
# ans2 += l
while l < N-1 and S[l+1] == 1:
    l += 1
while 0 <= r and S[r] == 0:
    r -= 1
# ans2 += N-r-2
while 0 < r and S[r-1] == 1:
    r -= 1
while l < r and k < K:
    k += 1
    ans2 += 2
    l += 1
    r -= 1
    while l < r and S[l] == S[l+1]:
        l += 1
    while l < r and S[r-1] == S[r]:
        r -= 1
print(max(ans1, ans2, f*N-1))

Submission status: Accepted

Solution code:
def d_face_produces_unhappiness():
    N, K = [int(i) for i in input().split()]
    S = input()
    before_char = S[0]
    t = []
    v = 0
    for s in S + '*':
        if s != before_char:
            t.append(v)
            v = 1
        else:
            v += 1
        before_char = s
    t.sort(reverse=True)
    for i in range(min(K, len(t))):
        t[i] += 2
    return min(sum([e - 1 for e in t]), N - 1)

print(d_face_produces_unhappiness())

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
N, K = LI()
S = input()

"""

答えは0以上N-1以下になる
まず何回ひっくり返せるかが重要
N==Kなら、全部ひっくり返して最大値となる
K==N-1なら、最大値から1箇所は矛盾する
LLRRLLなら
LLはRRになる
愚直回は、毎回どの区間をひっくり返すかを探索する
そうすると、区間の選び方だけでもかなり多い
好きな回数だけ選ぶと
まず塊の場所を特定する
6 1
LRLRRL
なら
てかどちらに統一するか問題もある
RRを
一番つながってるやつをひっくり返すのでいいか
Lにする場合とRにする場合を分けて考える
上のやつなら
Lにする場合
RRを返して
LRLLLL
で3
Rにする場合
LRRRRLになって3となる

9 2
RRRLRLRLL
の場合
Lの場合
LLLLRLRLL
になり、
LLLLLLRLL
5
Rの場合
111110101
111111101

長さをリストにすると
3, 1, 1, 1, 1, 2
最大にすると
5, 1, 1, 1, 1
6, 1, 1, 1

3, 1, 1, 1, 1, 2
3 1 1 4
7 1 1
RRRLRLLLL
LRLLLLLLL
だと6
RRRRRLRLL
RRRRRRRLR

LRLLLLRLL
LRLLLLLLL

RRRRLRRLL
RRRRRRLLR

RRRLLRLLL
RRRRRRLRR

RRRRRLRLR
RRRRRRLRR

-- RRRLRLRLL

RRRLRRRLR
LLLLRRRRR


長さをリストにすると
3, 1, 1, 1, 1, 2
3 3 1 2
3 6
2 + 5

RRRLLLRLL
RRRLLLLLL

まず、リストを作成

3 1 1 4
3 3 1 2
RRR LLL R LL
3 6
2 + 5
または


5 1 1 1


5 3
4 + 2

最小値の組み合わせをあわせる？
2個ずつ減っていく

LRLRRL
の場合
1 1 1 2 1
3 2 1
2+1 = 3
1 1 4 = 3

3 2 1
6
何回裏返せるかで決まってる

塊の数が
6子なら
6
4
26子なら
6
4
26子なら
6
4
26子なら
6
4
26子なら
6
4
26子なら
6
4
2
というふうに減っていく
4塊の場合はもう決まってる
3 3 1 2 = 5
3 1 1 4 = 5

-- RRRLRLRLL
3 1 1 1 1 2
6塊
まず9-6
ほんで3あまってる
答えは必ず3

"""
tmp = 1
l = []
for i in range(N-1):
    if S[i] == S[i+1]:
        if i == N - 2:
            tmp += 1
            l.append(tmp)
        else:
            tmp += 1
    else:
        if i == N - 2:
            l.append(tmp)
            l.append(1)
        else:
            l.append(tmp)
            tmp = 1
#  print(l)

len_l = len(l)
len_l -= 2 * K
if len_l <= 1:
    print(N - 1)
    exit()
elif len_l <= 2:
    print(N - 2)
else:
    ans = N - len_l
    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
    
ans=n-count-1

for i in range(k):
  if ans<n-2:
    ans+=2
  elif ans==n-2:
    ans+=1
  

print(ans)

Submission status: Accepted

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

out = 0
prev_letter = ''
for letter in S:
    if letter == prev_letter:
        out += 1
    prev_letter = letter

change = N - out - 1

if change >= 2 * K:
    out += 2*K
else:
    out = N - 1
    
print(out)

Submission status: Accepted

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

L = []
#L2 = []
cnt = 1
for i in range(1,N+1) :
    if S[i] != S[i-1] :
        L.append(cnt)
        #L2.append(cnt-1)
        cnt = 1
    else :
        cnt += 1

#print(L)

ans = 0

calc = sum(L) - len(L)

if len(L) <= 2*K + 1 :
    ans = sum(L)-1
else :
    su = sum(L[0:0+2*K+1])
    d = su
    c = calc + d - 1 - (d - (2*K+1))
    ans = max(ans,c)

    for i in range(2*K+1,N) :
        if i >= len(L) : break
        #d = sum(L[i:i+2*K+1])
        d += L[i]
        d -= L[i - (2*K+1)]
        c = calc + d - 1 - (d - (2*K+1))
        ans = max(ans, c)
        #print(i,i*2+1,c,calc,d)

print(ans)

Submission status: Accepted

Solution code:
n,k=[int(j) for j in input().split()]
s=input()
l=[1]
for i in range(1,n):
    if s[i]==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)
if len(l)//2<=k:
    print(n-1)
    exit()
ans=sum(l)-len(l)
ans+=2*k
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
N, K = [int(x) for x in input().split()]

def point(sl, num):
  p = ''
  ret = 0
  for i, s in enumerate(sl):
    if s == p:
      ret += num[i]
    else:
      ret += num[i] - 1
  return ret
  
S = input()
num = deque([])
sl = deque([])
c = 0
pre = S[0]
for s in S:
  if s == pre:
    c += 1
  else:
    sl.append(pre)
    num.append(c)
    pre = s
    c = 1
else:
  sl.append(pre)
  num.append(c)
  
if sl.count('R') > sl.count('L'):
  f = 'L'
  t = 'R'
else:
  f = 'R'
  t = 'L'

k = 0
sl2 = deque([])
num2 = deque([])
pre = sl[0]
c = 0
for i, s in enumerate(sl):
  if s == pre:
    c += num[i]
  else:
    if k < K:
      c += num[i]
      k += 1
    else:
      sl2.append(pre)
      num2.append(c)
      pre = s
      c = num[i]
else:
  sl2.append(pre)
  num2.append(c)
print(point(sl2, num2))

Submission status: Accepted

Solution code:
b = input().split()
n = int(b[0])
k = int(b[1])
r = 0
s=list(input())
for i in range(n-1):
    if(s[i] == s[i+1]):
        r += 1
t = n - r
if(k*2 < t):
    print(r + k*2)
else:
    print(n-1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S_temp = input()
S = [c for c in S_temp]

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

#change += 1
happy2 = min(K, (change // 2)) * 2
if change % 2 == 1 and K > change // 2:
  happy2 += 1
print(happy + happy2)

Submission status: Accepted

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

ans = 0
change = 0

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


for _ in range(k):
    if change >1:
        ans +=2
        change -=2
    elif change ==1:
        ans +=1
        change -=1
    else:
        break

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:i+1]!=S[i+1:i+2]:
        cnt += 1

if cnt//2 + 1 <= K:
    print(N-1)
else:
    print((N-1) - cnt + 2*K)

Submission status: Accepted

Solution code:
from itertools import groupby
N,K = list(map(int,input().split()))
S = input()
A = []

for i,j in groupby(S):
  A.append(len(list(j))-1)

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

Submission status: Accepted

Solution code:
n, k = [int(item) for item in input().split()]
s = input().rstrip()

cnt = 0
ans = 0
for p, q in zip(s, s[1:]):
    if p != q:
        cnt += 1
    else:
        ans += 1
ans += min(k*2, cnt)
print(ans)

Submission status: Accepted

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

tmp = s[0]
count = 1
for i in range(1,n):
  if s[i] == tmp:
    count += 1
  else:
    tmp = s[i]
    ls.append(count)
    count = 1
ls.append(count)

length = len(ls)
for i in range(k):
  if length==1: break
  tmp = 0
  if length == 2:
    ls = [ls[0]+ls[1]]
    break
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls[0] += tmp
    length -= 2
  
print(n-len(ls))

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
def gau(n):
    return (n-1)*(n-2)//2

def main():
    N,K = list(map(int,input().split()))
    S = str(input().rstrip())
    LS = len(S)
    SS = "R" + S + "L"
    ans = 0
    for i in range(1,LS+1):
        if SS[i] == "L" and SS[i-1] == "R":
            ans += 1
        elif SS[i] == "R" and SS[i+1] == "L":
            ans += 1
    print(min(N-1,N-ans+2*K))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = str(input())
L = []
R = []

if s == "L"*n or s == "R"*n:
    print(n-1)
    exit()
now = "E"
ss = 0
for i in range(n):
    if s[i] != now:
        if s[i] == "R" and ss:
            L.append(ss)
        elif s[i] == "L" and ss:
            R.append(ss)
        ss = 1
        now = s[i]
    else:
        ss += 1
    if i == n-1:
        if s[i] == "R" and ss:
            R.append(ss)
        elif s[i] == "L" and ss:
            L.append(ss)
lis = []
ri = 0
li = 0
if s[0] == "R":
    key = 0
else:
    key = 1
for i in range(len(R)+len(L)):
    if key == 0:
        lis.append(R[ri])
        ri += 1
        key = 1
    else:
        lis.append(L[li])
        li += 1
        key = 0


if len(lis) == 2:
    print(sum(lis)-1)
    exit()

m-=1
ans = 0

for i in range(3):
    ans += lis.pop(0)
for i in range(m):
    try:
        ans += lis.pop(0)
    except:
        continue
    try:
        ans += lis.pop(0)
    except:
        continue
ans -= 1
for nu in lis:
    ans += nu-1
print(ans)

Submission status: Accepted

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

# 1回のチェンジで全体の幸福度は1または2上昇させることができる
# 幸福度の最大はN-1
# これらから残りの試行で可能な最大幸福度をもとめる

# 現在の幸福度を出す

koufuku = 0

for i in range(N):
    if S[i] == 'L':
        if i == 0:
            continue
        if S[i-1] == 'L':
            koufuku += 1
    else:
        if i == N-1:
            continue
        if S[i+1] == 'R':
            koufuku += 1

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

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split(' '))
    b=list(input())
    ans = 0
    cnt = 0
    tmp = b[0]
    for i in range(1,n):
        if tmp == b[i]:
            ans += 1
        else:
            cnt += 1
            tmp = b[i]
    print(ans+min(2*k,cnt))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    np = N - ans - 1

    for k in range(K):
        if np > 1:
            ans += 2
            np -= 2
        elif np == 1:
            ans += 1
            np -= 1

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

MAX = 10**5+1

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

pare = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        pare += 1

min_pare = max(pare - 2*k, 1)

print(n-min_pare)

Submission status: Accepted

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

w = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        w += 1
        
c = w-2*K
if c <= 0:
    print(N-1)
else:
    print(N-c-1)

Submission status: Accepted

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

R=0
c=0
f=2
for i in range(N):
    if S[i]=='R':
        R+=1
        if f==0:
            c+=1
        f=1
    else:
        if f==1:
            c+=1
        f=0

out=min(N-c-1+2*K,N-1)

print(out)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    s = input()
    prev, seq = '0', 0
    a = []
    for c in s:
        if prev == c:
            seq += 1
        else:
            a.append(seq)
            seq = 1
        prev = c
    a.append(seq)
    a = a[1:]
    if len(a) // 2 <= k:
        print(n - 1)
        return
    b = [sum(a[:2 * k + 1])] + a[2 * k + 1:]
    ans = 0
    for m in b:
        ans += m - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

x = N - ans
if x%2 == 0:
    ans += min(2*K, x-1)
else:
    ans += min(2*K, x-1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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