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:
# 2019-11-18 00:38:19(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
import numpy as np 

def main():
    n, k = [int(x) for x in sys.stdin.readline().split()]

    s = np.array(list(sys.stdin.readline().rstrip()), dtype='U1')
    # dtype=U1 : Unicode, 1-char string.

    happy_count = np.count_nonzero(s[:-1] == s[1:])
    # s[:-1] と s[1:] の各要素を比較してTrue/False のndarray(n-dimensional array を返す) 
    # np.count_nonzeroでcount(bool(elem) != False)を返す

    happy_count += 2 * k
    # every rotation make more two or one person happy.(editorial)

    happy_count = min(happy_count, n - 1)
    # finaly, at least one person is unhappy

    print(happy_count)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

score = 0
preS_i = S[0]
mukiatteru = 0
hanareatteru = 0

for i in range(1,N):
  if S[i] == preS_i:
    score += 1
  else:
    if S[i] == "L":
      mukiatteru += 1
    else:
      hanareatteru += 1
    preS_i = S[i]

if min(mukiatteru, hanareatteru) >= K:
  score += 2*K
else:
  score += min(mukiatteru, hanareatteru) + min(K, max(mukiatteru, hanareatteru))
print(score)

Submission status: Accepted

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    # See:
    # https://www.youtube.com/watch?v=VSeggcnxwrc

    # KeyInsight
    # L, Rでまとめる
    # 1回の操作で幸福度が最大で2増える
    # 操作したときの内部のスコアが変化しない
    # 例外的に，すべて同じ文字の場合は変化せず，ランレングス圧縮したときに2グループのときは1増える
    # min(理論値n - 1, 初期スコア + 2 * k回)

    # つまづきポイント
    # 反転操作で，スコアが変化する/変化しない部分を明らかにする
    # 操作が1回の場合を考えて，多数回に展開
    # スコアを増やす=異なるグループを減らす

    # どうしたら気がつけそうか?
    # 同じ要素をまとめる
    # 操作を言い換える，同じことを違う言葉で表現する/異なる視点で見る
    # 理論値VS初期値 + 操作による変化を比べる

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

happy = 0
ncc = 1 # number of connected components
for i in range(N - 1):
    ncc += S[i] != S[i + 1]
if ncc >= 3:
    p = min(K, (ncc - 1) // 2)
    ncc -= 2 * p
    K -= p
if ncc == 2 and K > 0:
    ncc -= 1
print(N - ncc)

Submission status: Accepted

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

happy = 0
ncc = 1 # number of connected components
for i in range(N):
    if S[i] == 'L':
        if i > 0 and S[i - 1] == 'L':
            happy += 1
    elif S[i] == 'R':
        if i < N - 1 and S[i + 1] == 'R':
            happy += 1
    if i > 0 and S[i] != S[i - 1]:
        ncc += 1
if ncc >= 3:
    p = min(K, (ncc - 1) // 2)
    ncc -= 2 * p
    happy += 2 * p
    K -= p
if ncc == 2 and K > 0:
    happy += 1
print(happy)

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

Submission status: Accepted

Solution code:
def main():
  N, K = map(lambda i: int(i), input().split(' '))
  S = list(input())
  score = 0
  for i in range(N):
    if i >= 1 and S[i] == 'L' and S[i - 1] == 'L':
      score += 1
    elif i <= N - 2 and S[i] == 'R' and S[i + 1] == 'R':
      score += 1
  print(min(N - 1, score + 2 * K))

main()

Submission status: Accepted

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

    count = 0
    first_char = S[0]
    before_char = first_char
    if first_char == 'L':
        not_first_char = 'R'
    else:
        not_first_char = 'L'
    for i in range(1,n):
        if count == k:
            break
        if S[i] == first_char:
            if before_char == first_char:
                continue
            else:
                before_char = first_char
                count += 1
        else:
            if before_char == first_char:
                S[i] = first_char
                before_char = not_first_char
            else:
                S[i] = first_char
                continue

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if (count-1) / 2 <= K:
    print(N-1)

else:
    print(N - (count - 2*K))

Submission status: Accepted

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

l = 0
r = 0
count = 0
hcount = 0
score = 0
def sccount(s):
    l = 0
    r = 0
    count = 0
    score = 0
    for i in range(n):
        if s[i] == 'R':
            if r == 1:
                score += 1
            l = 0
            r = 1
        else:
            if l == 1:
                score += 1
            l = 1
            r = 0
    l = 0
    r = 0
    return score

if s[0] == 'L':
    for i in range(n):
        if s[i] == 'L':
            if r == 1 :
                count += 1
            l = 1
            r = 0
        else:
            l = 0
            r = 1
    if s[-1] == 'R':
        hcount = 1
else:
    for i in range(n):
        if s[i] == 'R':
            if l == 1 :
                count += 1
            l = 0
            r = 1
        else:
            l = 1
            r = 0
    if s[-1] == 'L':
        hcount = 1
score = sccount(s)
if count >= k:
    ans = score + k*2
elif count < k:
    ans = score + count*2 + hcount
print(ans)
# print(score,count,hcount)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
last = None
total = 0
for c in S:
    if c != last:
        total += 1
    last = c
print(N-max(1, total - 2 * K))

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]
S = input()
memo = S[0]
count = 0
total = 0
cntDict= dict.fromkeys([int(i) for i in range(1,N+1)],0)


for s in S:
    if s == memo:
        count +=1
    else:
        cntDict[count] += 1
        count = 1
    memo = s
cntDict[count] += 1
changeCnt = sum(cntDict.values())

for k,v in cntDict.items():
    if v == 0 and k == 1:
        continue
    
    total += (k-1)*v
        
if changeCnt//2 <= K:
    total = N-1
else:
    total += 2*K
        

print(total)

Submission status: Accepted

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

    #幸せな人の数
    h = 0 
    s1 = 'S'
    for s in S:
        if s == s1:
            h += 1
        s1 = s

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
li = list(input())
a = 0
b = 0
for i in range(N-1):
  if li[i] == li[i+1]:
    b += 1
  else:
    a += 1
for j in range(K):
  if a >= 2:
    a -= 2
    b += 2
  elif a == 1:
    a -= 1
    b += 1
  else:
    break
print(b)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


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


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    N = I()
    print(pow(N, 3))
    return


# B
def B():
    N = I()
    A = LI()
    B = LI()
    C = LI()
    a_p = -1
    ans = 0
    for a in A:
        if (a - a_p == 1):
            ans += B[a - 1] + C[a - 2]
        else:
            ans += B[a - 1]
        a_p = a
    print(ans)
    return


# C
def C():
    N = I()
    B = LI()
    A = [0 for i in range(N)]
    A[0] = B[0]
    A[N - 1] = B[N - 2]
    for i in range(1, N - 1):
        A[i] = min(B[i - 1], B[i])
    print(sum(A))
    return


# D
def D():
    n,k=LI()
    s=S()
    cnt1=0
    cnt2=0
    i_pre=''
    if(s[0]=='L'):
        cnt1+=1
    if(s[n-1]=='R'):
        cnt1+=1
    for i in s:
        if i_pre=='R' and i=='L':
            cnt2+=1
        i_pre=i
    ans=n-cnt1-2*cnt2
    if cnt1==0:
        if k<=cnt2-1:
            print(ans+2*k)
        else:
            print(n-1)
    if cnt1==1:
        if k<=cnt2:
            print(ans+2*k)
        else:
            print(n-1)
    if cnt1==2:
        if k<=cnt2:
            print(ans+2*k)
        else:
            print(n-1)
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()
    return


# Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, K = map(int, input().strip().split())
    S = input().strip()
    before = S[0]
    count = 0
    score = N
    for s in S[1:]:
        if before == "R" and s == "L":
            count += 1
        before = s
    if S[0] == "L":
        score = N - 1 - 2*max(count-K, 0)
        if S[-1] == "R":
            if count - K < 0:
                pass
            else:
                score -= 1
    else:
        score = N - 2*max(count-K, 0)
        if count - K <= 0:
            score -= 1
        else:
            if S[-1] == "R":
                score -= 1
    print(score)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(input())
a=[]
b=1
for i in range(len(l)-1):
    if l[i]==l[i+1]:
        b=b+1

    else:
        a.append(b)
        b=1

if l[n-2]==l[n-1]:
    a.append(b)
else:
    a.append(1)


if len(a)//2<k:
    print(n-1)

elif len(a)/2==k:
    print(sum(a)-len(a)+k*2-1)

else:
    print(sum(a)-len(a)+k*2)

Submission status: Accepted

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

i = 0
ss = list()
while i < n:
    cnt = 1
    c = s[i]
    while i < n-1 and s[i] == s[i+1]:
        cnt += 1
        i += 1
    i += 1
    ss.append((c, cnt))

ans = 0
if len(ss) // 2 >= k:
    for j in range(k):
        ss[2 * j + 1] = ('L', ss[2*j+1][1]) if ss[2*j+1][0] == 'R' else ('R', ss[2*j+1][1])
    s = ''.join([''.join([x[0] for _ in range(x[1])]) for x in ss])
    for x in range(len(s)-1):
        if s[x] == s[x+1]:
            ans += 1
else:
    ans = len(s) - 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input()
i = 0
while len(s) > i + 1:
    if s[i] == s[i + 1]:
        s = s[:i] + s[i + 1:]
    else:
        i += 1

ans = len(s)

for i in range(k):
    if ans > 2:
        ans -= 2
    elif ans == 1:
        break
    elif ans == 2:
        ans = 1

ans = n - ans

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import groupby

n,k = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()

kohuku = 0

for i in range(len(s)-1):
    if s[i] == "R" and s[i+1] == "R":
        kohuku += 1
    elif s[i] == "L" and s[i+1] == "L":
        kohuku += 1

if len(s) == 1:
    print(0)
    exit()

num_2 = s.count("RL")

num_1 = 0
if s[0] == "R":
    num_1 += 1
elif s[-1] == "R":
    num_1 += 1
if k <= num_2:
    print(min(n-1,2*k+kohuku))
    exit()

if num_1 == 0:
    print(min(n-1,2*k+kohuku))

elif num_1 == 1:
    print(min(n-1,2*num_2+1+kohuku))

else:
    if k == num_2 +1:
        print(min(n-1,2*num_2+1+kohuku))
    else:
        print(min(n-1,2*num_2+2+kohuku))

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import groupby

n,k = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()

kohuku = 0

for i in range(len(s)-1):
    if s[i] == "R" and s[i+1] == "R":
        kohuku += 1
    elif s[i] == "L" and s[i+1] == "L":
        kohuku += 1

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

Submission status: Accepted

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

def ranlength(A):
    num = list(A)
    count = 1
    table = []
    for i in range(len(num)):
        try:
            if num[i] == num[i+1]:
               count = count + 1
            else:
                table.append(count)
                count = 1
        except:
            table.append(count)
    return(table)

RL=ranlength(S)
a=0
for i in RL:
    a+=i-1

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

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, K = IL()
s = S()

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().strip().split())
S = input().strip()
cnt = 0
for i in range(1, N):
  if S[i-1] == S[i]:
    cnt += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

happy_face = N - 1 - S.count('LR') - S.count('RL')
ans = min(N - 1, happy_face + 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(len(s)-1,ans+2*k))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()
i=0
a=0
for i in range(n-1):
  if S[i]==S[i+1]:
    a=a+1
    i=i=1
  else:
    i=i+1
for j in range(k):
  if a<=(n-3):
    a=a+2
    k=k+1
  elif a==(n-2):
    a=a+1
    k=k+1
  else:
    k=k+1
print(a)

Submission status: Accepted

Solution code:
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, K = LI()
S = str(input())
ans = int(0)

R = []
L = []
before = "R"
if S[0]=="L":
    R.append(0)
    before = "L"
cur = int(0)
for s in S:
    if before==s:
        cur +=1
    else:
        if s=="L":
            R.append(cur)
            before = "L"
            cur = int(1)
        else:
            L.append(cur)
            before = "R"
            cur = int(1)

if s == "L":
    L.append(cur)
else:
    R.append(cur)

#print(R,L)
Rlen = len(R)
Llen = len(L)
#ansC = []
#for i in range(Rlen-K):
#    cur = int(0)
#    for j in range(K+1):
#        cur += R[i+j]
#    for j in range(K):
#        cur += L[i+j]
#    ansC.append(cur)
#for i in range(Llen-K):
#    cur = int(0)
#    for j in range(K):
#       cur += R[i+j+1]
#    for j in range(K+1):
#        cur += L[i+j]
#    ansC.append(cur)
#print(ansC)

ans = min(N-1, 2*K+sum(R)+sum(L)-Rlen-Llen)
if S[0]=="L":
    ans +=1
ans = min(N-1,ans)
print(ans)

Submission status: Accepted

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




happies = 0
happy_max = N-1

for i in range(N-1):
    if (S[i] == 'R') & (S[i+1] == 'R'):
        happies +=1
    if (S[-i-1] == 'L') & (S[-i-2] == 'L'):
        happies +=1
print(min(happies+2*K,happy_max))

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    a=input()
    i=0
    cnt=1
    l=[]
    while i<n-1:
        if a[i]!=a[i+1]:
            l.append(cnt)
            cnt=1
        else:
            cnt+=1
        i+=1
    l.append(cnt)
    print(min(n-len(l)+2*k,n-1))
main()

Submission status: Accepted

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

Submission status: Accepted

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

s = input()

cnt = 0

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
partition = 1
for a, b in zip(S, S[1:]):
    if a != b:
        partition += 1

print(min(N - 1, N - (partition - (2 * K))))

Submission status: Accepted

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

B = input()
C = []
for i in range(N-1):
    if B[i]!=B[i+1]:
        C.append(B[i])
C.append(B[N-1])

if len(C) % 2 == 1:
    print(min(M,len(C)//2)*2+N-len(C))
else:
    if M<len(C)//2:
        print(M*2+N-len(C))
    else:
        print(len(C)+N-len(C)-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    ls = []
    cnt = 1
    for i in range(1, n):
        if s[i] != s[i-1]:
            ls.append(cnt-1)
            cnt = 1
        else:
            cnt += 1
    ls.append(cnt-1)
    print(min(n-1, sum(ls) + k * 2))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,k=map(int, input().split()) 
s=list(input())
s=list('R')+s+list('L')
count1=0
count2=0

for i in range(1,n+2):
    if s[i-1]=='R' and s[i]=='L':
        if i==1 or i==n+1:
            count1+=1
        else:
            count2+=1
            
ans=n-(count1+count2*2)

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

Submission status: Accepted

Solution code:

N, K = [int(item) for item in input().split()]
S = [item for item in input()]

def compress(arr):
    """圧縮して消えた人はhappy"""
    cnt_h = 0
    new_arr = []
    comp_arr = ['L']

    #最初は先頭をLにする　この回転はノーカン
    if arr[0] == 'R':
        for item in arr:
            if item == 'L':
                new_arr.append('R')
            else:
                new_arr.append('L')

            prev_item = item
    else:
        new_arr = arr
    # 圧縮操作と圧縮されたかずを数える

    for i in range(1, N):
        if new_arr[i - 1] == new_arr[i]:
            cnt_h += 1
        else:
            comp_arr.append(new_arr[i])

    return [comp_arr, cnt_h] 


def execute(arr, cnt_h, K):
    # 境界を全て反転するために必要な操作回数
    max_rotation = len(arr)//2
    # 全てLになるか反転回数がKに到達するかで終了
    if max_rotation <= K:
        cnt_h += len(arr) - 1
    else:
        cnt_h += 2*K

    return cnt_h

arr, cnt_h = compress(S)
print(execute(arr, cnt_h, K))

Submission status: Accepted

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

def compress(arr):
    """圧縮して消えた人はhappy"""
    cnt_h = 0
    new_arr = []
    comp_arr = ['L']

    #最初は先頭をLにする　この回転はノーカン
    if arr[0] == 'R':
        for item in arr:
            if item == 'L':
                new_arr.append('R')
            else:
                new_arr.append('L')

            prev_item = item
    else:
        new_arr = arr
    # 圧縮操作と圧縮されたかずを数える

    for i in range(1, N):
        if new_arr[i - 1] == new_arr[i]:
            cnt_h += 1
        else:
            comp_arr.append(new_arr[i])

    return [comp_arr, cnt_h] 


def execute(arr, cnt_h, K):
    # 境界を全て反転するために必要な操作回数
    max_rotation = len(arr)//2
    # 全てLになるか反転回数がKに到達するかで終了
    if max_rotation <= K:
        if arr[-1] == 'R':
            cnt_h += max_rotation*2 -1
        elif arr[-1] == 'L':
            cnt_h += max_rotation*2
    else:
        if arr[2*K] == 'R':
            cnt_h += 2*K - 1
        elif arr[2*K] == 'L':
            cnt_h += 2*K

    return cnt_h

arr, cnt_h = compress(S)
print(execute(arr, cnt_h, K))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
list1 = list(input())

first,last = 0,0 #しゃくとり法の、firstとlast
count = 0
flag = 1 #2変更毎にスワップしてく為
#操作１、変更できる部分についてのループ
#時間削減のため、わざわざリストを操作しない。どこまでしゃくとれたかで考える
for i in range(m+1): #変更可能回数+1だけループ(理由：変更したあとの、次の変わり目でループを止めたい)
	if first == n:
		break
	while True:
		if first == n:
			break
		if list1[first] != list1[last]:
			if flag:
				last = first
				first += 1
				flag = 0
				break
			else:
				flag = 1
				last = first
				if i == m:
					first += 1
					break #フラグ分ループ回数が多くなるから。本来は"理由："の為に止めたい
				
				
		first += 1

if first == n: #全ての要素が同一になったなら
	print(n-1)
	exit()

#操作２、変更でどれだけカウントが増えたのか計上。
#整理：lastは現在変わり目地点(変わったあと)にいる。
count += last -1 +1 #カウントは人数-1,なお、インデックスの概念が存在するので+1

#操作3、変更できない部分について地道にしゃくとりでカウント。
#なお、first,lastは引き継ぐことができる。
while True:
	if first == n:
		break
	while True:
		if first == n:
			count += first - last -1 #firstがnを超えてるので、一個戻す。
			break
		if list1[first] != list1[last]:
			count += first - last -1
			last = first
			first += 1
			break
		first += 1

print(count)

Submission status: Accepted

Solution code:
def main():
# input
    N, K = map(int, input().split())
    b = input()

# loop
    num = 0
    for i in range(len(b)-1):
        if b[i] != b[i+1]:
            num += 1
    print(min(N-1, N-1-num+2*K))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# 初期の幸せ度を調べる
happiness = 0
previous_face = S[0]
for i in range(1, N):
    if S[i] == previous_face:
        happiness += 1
    else:
        previous_face = S[i]

# 並べ替え後の幸せ度
happiness = happiness + 2 * K
if N - 1 < happiness:
    happiness = N - 1

# 出力
print(happiness)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, K = map(int, input().split())
    string = input()
    count = 0
    for idx in range(N - 1):
        if string[idx] == string[idx + 1]: count += 1
    print(min(N - 1, count + 2 * K))

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 - 1] == S[i]:
        ans += 1
ans = min(N - 1, ans + 2 * K)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
S=input()
RL=S.count('RL')
LR=S.count('LR')
diff=RL+LR
happy=N-1-diff
if diff%2==0:
    print(happy+2*min(diff//2,K))
else:
    print(happy+2*K if (diff//2+1)>K else happy+diff)

Submission status: Accepted

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

RL = s.count('RL')
LR = s.count('LR')
diff = RL + LR

cnt = (N-1) - diff

for i in range(K):
    if diff >= 2:
        diff -= 2
        cnt += 2
    elif diff == 1:
        diff -= 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
group = 1
#print('s[1:]'+s[1:])


for c, d in zip(s, s[1:]):
	if c != d:
		group += 1
	#L,Rの連続してないところが何個あるか求める＝group
	#１回で２つ直せるから,2 * k
	#n(文字数)-直せなかった連続してない数
print(min(n - 1, n - (group - 2 * k)))
#先頭は幸福でないから最高でもn-1
#

Submission status: Accepted

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

RL = s.count("RL")
KADO = 0
if s[0] == "L":
    KADO += 1
if s[-1] == "R":
    KADO += 1

if k < RL:
    RL -= k
elif k > RL and KADO == 2:
    RL = 0
    KADO -= 1
else:
    RL = 0

if RL + KADO == 0:
    KADO =1

print(n-(RL*2 + KADO))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
pre = 0
sepS = []
happyCount = 0
RLcount = 0
for i in range(1, n):
    if s[i] == s[i - 1]:
        happyCount += 1
    if s[i] == 'L' and s[i - 1] == 'R':
        RLcount += 1
#print("now HP =>{}".format(happyCount))
happyCount += min(k, RLcount) * 2
if k > RLcount:
    happyCount += 1
print(min(n - 1, happyCount))

Submission status: Accepted

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

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

Submission status: Accepted

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

Unhappy = {}
Unhappy[1] = 0
Unhappy[2] = 0

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

if Unhappy[1] == 0:
    act = min(K, Unhappy[2] - 1)
    K -= act
    Unhappy[2] -= act
    if K != 0:
        K -= 1
        Unhappy[2] -= 1
        Unhappy[1] += 1
else:
    act = min(K, Unhappy[2])
    K -= act
    Unhappy[2] -= act
    if Unhappy[1] == 2 and K != 0:
        K -= 1
        Unhappy[1] -= 1

print(N - Unhappy[1] - Unhappy[2] * 2)

Submission status: Accepted

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

def flip(l, r):
    for i in range((r + l) // 2 - l + 1):
        tmp = S[l + i]

        S[l + i] = 'R' if S[r - i] == 'L' else 'L'
        S[r - i] = 'R' if tmp == 'L' else 'L'


def f(w, start):
    l_idx = -1
    for i in range(start, N - 1):
        if S[i] == w[0] and S[i + 1] == w[1]:
            l_idx = i
            break

    if l_idx < 0: return -1
    r_idx = -1

    for i in range(l_idx + 1, N - 1):
        if S[i] == w[1] and S[i + 1] == w[0]:
            r_idx = i
            break
    if r_idx < 0: return -1

    flip(l_idx + 1, r_idx)
    return l_idx + 1


cnt = 0
for LR in ['LR', 'RL']:
    l = 0
    while cnt < K and l >= 0 and l < N - 1:
        l = f(LR, l)
        if l >= 0: cnt += 1

l = 0
for i in range(N - 1):
    if cnt >= K: break

    if S[i] != S[i + 1]:
        flip(l, i)

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

Submission status: Accepted

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

cnt = 0
l = 1

def f(w, start):
    l_idx = -1
    # while
    for i in range(start, N - 1):
        if S[i] == w[0] and S[i + 1] == w[1]:
            l_idx = i
            break

    if l_idx < 0: return -1
    r_idx = -1

    for i in range(l_idx + 1, N - 1):
        if S[i] == w[1] and S[i + 1] == w[0]:
            r_idx = i
            break

    if r_idx < 0: return -1

    for i in range(l_idx + 1, r_idx + 1):
        S[i] = 'R' if S[i] == 'L' else 'L'

    return l_idx + 1


cnt = 0

l = 1

while cnt < K and l > 0 and l < N - 1:
    l = f('LR', l)
    if l > 0: cnt += 1

l = 1
while cnt < K and l > 0 and l < N - 1:
    l = f('RL', l)
    if l > 0: cnt += 1

l = 0
for i in range(N - 1):
    if cnt >= K: break

    if S[i] != S[i + 1]:
        for j in range(l,i+1):
            S[j] = 'R' if S[j] == 'L' else 'L'
        cnt += 1
        l=i+1

m = 0
pre = ''
ans = 0
for i in range(N):
    if pre == S[i]:
        m += 1
    else:
        ans += m
        m = 0
        pre = S[i]
ans += m
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

#output
#最初にhappyな人の数を計算
happy = 0

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

#happyになれる人数の最大値はN-1
#1回の操作で+2人happyにできる
if happy + 2*K < N-1:
    print(happy + 2*K)
else:
    print(N-1)

Submission status: Accepted

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

tmp = A[0]
cnt = 1
for i in range(1,N):
	if A[i] == tmp:
		continue
	else:
		tmp = A[i]
		cnt += 1

ans = N - (cnt - (2*K))

print(min(N-1, ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lr = list(input())
j = 0
counts = [0]
for i in range(n):
    if lr[j] == lr[i]:
        counts[-1] += 1
    else:
        j = i
        counts.append(1)

for _ in range(k):
    if len(counts)>=3:
        counts[0] += counts[1]+counts[2]
        del counts[1:3]
    elif len(counts)==2:
        counts[0] += counts[1]
        del counts[1]
    else:
        break

count = sum(counts) - len(counts)
print(count)

Submission status: Accepted

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

prev = s[0]
line = []
cnt = 1
for v in s[1:]:
    if v != prev:
        prev = v
        line.append(cnt - 1)
        cnt = 1
    else:
        cnt += 1
line.append(cnt - 1)

k = min(len(line) // 2, k)
print(sum(line) + k * 2 - (len(line) // 2 == k and len(line) % 2 == 0))