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 = ['R'] + list(input()) + ['L']

#print(s)

ans = 0

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

S = input()

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

b = 0
p1 = 0
p2 = 0
for i in range(N):
    if i == 0:
        if S[i] == S[i+1]:
            b += 1
        if S[i] == "L":
            p1 += 1
        else:
            if S[i] == "R" and S[i+1] == "L":
                p2 += 1
    elif 0 < i < N-1:
        if S[i] == S[i+1]:
            b += 1
        if S[i] == "R" and S[i+1] == "L":
            p2 += 1
    elif i == N-1:
        if S[i] == "R":
            p1 += 1

#print(b)
if K <= p2:
    b += 2*K
else:
    b += 2*K
    K -= p2
    b += max(p1, K)

print(min(N-1,b))

Submission status: Accepted

Solution code:
from sys import stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
count = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        count += 1
print(min(N-1, count+2*K))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
li=[]
seq=1
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        seq+=1
    else:
        li.append(seq)
        seq=1
        
li.append(seq)
length=len(li)
ans=sum(li)-length

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


print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

sc = 0
lr = 0
rl = 0

for i in range(n-1):
    c = s[i]
    nc = s[i+1]

    if c == nc:
        sc += 1
    elif c == 'L' and nc == 'R':
        lr += 1
    elif c == 'R' and nc == 'L':
        rl += 1

if rl == lr:
    dc = lr
    oc = 0
else:
    dc = min(lr, rl)
    oc = 1

if dc + oc <= k:
    print(dc*2 + oc + sc)
else:
    print(sc + k*2)

Submission status: Accepted

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

Submission status: Accepted

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

s_c = []

left = 0
right = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        right = i + 1
    else:
        s_c.append(''.join(s[left:right + 1]))
        i += 1
        left = i
        right = i
s_c.append(''.join(s[left:right + 1]))

s_c_len = len(s_c)
cc = 'R'
if s_c_len > 1 and s_c[1][0] == 'R':
    cc = 'L'

for i in range(k):
    if (2 * i + 1) > s_c_len - 1:
        break
    s_c[2 * i + 1] = cc * len(s_c[2 * i + 1])

ans_s = ''.join(s_c)
ans = 0
for i in range(n):
    if ans_s[i] == 'R' and i != n - 1 and ans_s[i + 1] == 'R':
        ans += 1
    elif ans_s[i] == 'L' and i != 0 and ans_s[i - 1] == 'L':
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,s=open(0);n,k=map(int,n.split());print(min(n-1,k*2+sum(i==j for i,j in zip(s,s[1:]))))

Submission status: Accepted

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

sc = 0
lr = 0
rl = 0

for i in range(n-1):
    c = s[i]
    nc = s[i+1]

    if c == nc:
        sc += 1
    elif c == 'L' and nc == 'R':
        lr += 1
    elif c == 'R' and nc == 'L':
        rl += 1

if rl > 1 or lr > 1:
    dc = min(lr, rl)
    oc = abs(lr-rl)
elif rl == 1 or lr == 1:
    dc = 0
    oc = 1
else:
    dc = 0
    oc = 0

dnum = min(k, dc)
onum = 0
if k - dc > 0 and oc == 1:
    onum += 1
print(onum + sc + dnum*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(n, k, s):
    s = list(map(lambda c: c=='L', s))
    i = 1
    while i < n:
        if (k > 0) and (s[i] != s[i-1]):
            l = i
            while (i+1 < n) and (s[i] == s[i+1]):
                i += 1
            r = i
            for j in range(l, r+1):
                s[j] = not s[j]
            k -= 1
        i += 1
    ans = 0
    for i in range(1, n):
        if s[i] == s[i-1]:
            ans += 1
    return ans

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, S: str):
    ret = 0
    cnt = 1
    tmp = 0
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            cnt += 1
        else:
            if cnt > 1:
                ret += cnt - 1
            cnt = 1
            tmp += 1
    ret += cnt - 1
    ret += min(K, tmp // 2) * 2
    if K > tmp // 2:
        ret += tmp % 2
    ret = min(ret, N - 1)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b=input().strip().split(' ')
a,b=[int(a),int(b)]
c=input().strip()
d=0
if c[0]=='R':
  if c[1]=='R':
    d+=1
  
for i in range(1,a-1):
  if c[i]=='L':
    if c[i-1]=='L':
      d+=1
  elif c[i]=='R':
    if c[i+1]=='R':
      d+=1
if c[a-1]=='L':
  if c[a-2]=='L':
    d+=1
d=d+2*b
if d>(a-1):
  print (a-1)
else:
  print(d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc139/tasks/abc139_c
# 整数の入力
n, k = map(int, input().split())
s = str(input())
c = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        c += 1

c = c + 2*k
print(c) if c < n-1 else print(n-1)

Submission status: Accepted

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

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

ans=c+2*K

if ans<=N-1:
  print(ans)
else:
  print(N-1)

Submission status: Accepted

Solution code:
n = input().split()
N,K = int(n[0]),int(n[1])
S = list(input())

count = 0
count_s1 = 0
count_sn = 0
s_1 = S[0]
if s_1 == "L":
    count_s1 += 1
s_N = S[-1]
if s_N == "R":
    count_sn += 1

for i in range(len(S)-1):
    if S[i] == "R" and S[i+1] == "L":
        count += 1

if K <= count:
    print(N - ((count-K)*2 + count_s1 + count_sn))
else:
    print(N-1)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
r = []
num = 1

# 文字列を固まりごとのリストに変換
for i in range(0, n-1):
  if s[i] == s[i+1]:
    num += 1
  else:
    r.append(num)
    num = 1
r.append(num)

# 幸福の最大値を算出
for j in range(k):
  if len(r) == 2:
    r[0] = r[0] + r[1]
    r.pop(1)
  elif len(r) == 1:
    pass
  else:
    r[0] = r[0] + r[1] + r[2]
    r.pop(2)
    r.pop(1)

ans = sum(r) - len(r)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = str(input())
cnt = 0
l = 0
r = 0

for i in range(N-1):
    if S[i] == "R" and S[i+1] == "L":
        cnt += 1
if S[0] == "L":
    l += 1
if S[N-1] == "R":
    r += 1
    
unhappy = 0
if cnt + max(l,r) <= K:
    unhappy = 1
else:
    unhappy = 2 * (cnt - K) + l + r
print(N - unhappy)

Submission status: Accepted

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

ans = 0
tmp_s = None
for s in S:
    if tmp_s == s:
        ans+=1
    tmp_s = s

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

before = s[0]
cnt=0

for current in s:
    if current != before:
        cnt += 1
    before = current

score_max = len(s)-1
print(min(score_max, score_max-cnt+k*2))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = [1 if ele=="L" else 0 for ele in input()]

before = s[0]
cnt=0

for si in s:
    if si != before:
        cnt += 1
    before = si

score_max = len(s)-1
print(min(score_max, score_max-cnt+k*2))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = [1 if ele=="L" else 0 for ele in input()]

if s[0]==0:
    s=[(1-ele) for ele in s]

before = s[0]
cnt=0
for si in s:
    if si != before:
        cnt += 1
    before = si

score_max = len(s)-1
print(min(score_max, score_max-cnt+k*2))

Submission status: Accepted

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

# 与えられた文字列の幸福度は、LとRの入れ替わりの数だけで決まることに着目
# 幸福度は、最初の方は2ずつ上げることができる。
# 端数が出る場合は最後に1だけ上げられる

#        change   happiness
# LLLLL  0        4
# LLLRR  1        3 -> 4
# LLRRL  2        2 -> 4
# LLRLR  3        1 -> 3 -> 4


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def solve(N, K, S):
    prev = S[0]
    change = 0
    for ch in S[1:]:
        change += ch != prev
        prev = ch

    happiness = N - 1 - change

    # K回のうち、use回を使って、幸福度をuse * 2上昇させる
    use = min(K, change // 2)
    happiness += use * 2
    K -= use

    # まだねじれがあれば修正
    if K > 0 and happiness != N - 1:
        happiness += 1

    return happiness


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

# assert solve(1, 1, "L") == 0
# assert solve(2, 1, "LR") == 1
# assert solve(2, 2, "LR") == 1
# assert solve(2, 2, "LL") == 1
# assert solve(3, 1, "LLL") == 2
# assert solve(3, 1, "LRL") == 2
# assert solve(3, 2, "LRL") == 2
# assert solve(3, 1, "LLR") == 2

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()
change_count = 0
first = S[0]
for i in range(1,N):
    if first != S[i]:
        change_count += 1
        first = S[i]
print(N - 1 - max(0,change_count-K*2))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():

    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((ans + 2 * K), N - 1))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K = MI()
    S = ST()
    before = "#"
    RLE = []
    for i,s in enumerate(S):
        if s != before:
            before = s
            RLE.append(1)                        
        else:
            RLE[-1]+=1
    ans = sum(RLE) - len(RLE) #すでに幸せ
    cnt = len(RLE)
    for i in range(K):
        if cnt >= 3:
            ans += 2
        elif  cnt == 2:
            ans += 1
        cnt -=1
        if not cnt:
            break
    print(min(ans,N-1))
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, k = getList()

s = input().strip()
s = s

state = "X"
cur_seq = 0
seq_nums = []
n_separate = 0


for c in s:
    # print(c, state == c)
    if state == c:
        cur_seq += 1
    else:
        state = c
        seq_nums.append(cur_seq)
        cur_seq = 1
        n_separate += 1


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

Submission status: Accepted

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

n_flip = 0
s_last = s[0]
for i in range(1, len(s)):
    if s[i] != s_last:
        n_flip += 1
    s_last = s[i]
    if n_flip % 2 == 1 and n_flip // 2 < k:
        s[i] = s[0]

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

print(n_happy)

Submission status: Accepted

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

last = ''
count = 0
face_count = 0
for i in range(len(s)):
    if i == 0: pass
    else:
        if s[i] == last:
            count += 1
        else:
            face_count += 0.5
    last = s[i]

if face_count > k:
    print(count + 2*k)
elif face_count <= k:
    print(n - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
happy = 0
try1 = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        happy += 1
while happy <= n - 2 and try1 < k:
    if happy <= n - 3:
        happy += 2
    else:
        happy += 1
    try1 += 1
print(int(happy))

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
S = input()
tmp = S[0]
cnt = 0
L = []
for x in S:
    if tmp == x:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
        tmp = x
L.append(cnt)
tmp = 0
for _ in range(b):
    for _ in range(2):
        try:
            tmp += L.pop(0)
        except:
            print(a- 1)
            quit()
try:
    tmp += L.pop(0)
except:
    print(a-1)
    quit()
L = [tmp] + L
print(sum(L) - len(L))

Submission status: Accepted

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

count = 0
ans = 0

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

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

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    c = s.count("RL") + s.count("LR")
    return str(int(n) - max(1, c + 1 - 2 * int(k)))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    n, k = map(int, [n, k])
    ans = n - 1 - s.count("RL") - s.count("LR")
    return str(min(ans + 2 * k, n - 1))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    k = int(k)
    ans = change = 0
    for s0, s1 in zip(s, s[1:]):
        if s0 == s1:
            ans += 1
        else:
            change += 1
    return str(ans + min(2 * k, change))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
# import pandas as pd
# import numpy as np

# d = pd.read_csv("useful.csv", usecols = ["Q133", "Q134", "Q146"])

# #l = d["Q133"]
# l = d["Q146"]
# bad = []
# good = [] 
# for i in range(1, 56):
# 	if int(l[i][0]) >= 4:
# 		good.append(i)
# 	else:
# 		bad.append(i)
# print(bad, good)

import sys
input = sys.stdin.readline

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import re
from collections import deque

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

token = re.findall(r'(L+|R+)', S)

def flip(s):
    if s[0] == 'R':
        return 'L'*len(s)
    else:
        return 'R'*len(s)
    
even = False
flipped_token = deque([])

flip_count = 0
for s in token:
    if flip_count >= K:
        flipped_token.append(s)
    else:
        if even:
            s = flip(s)
            flip_count += 1
            flipped_token.append(s)
            even = False
        else:
            flipped_token.append(s)
            even = True

flipped_S = ''.join(flipped_token)
        
token = re.findall(r'(L+|R+)', flipped_S)

happy_count = 0

for s in token:
    l = len(s)
    happy_count += l-1

print(happy_count)

Submission status: Accepted

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

s_comp = []
cnt = 1

#分解
for i in range(n):
    #最後だけ例外処理
    if i == n-1:
        if s[i-1] != s[i]:
            cnt = 1
            s_comp.append(str(s[i])*cnt)   
        else:
            s_comp.append(str(s[i])*cnt)  
    #同じならカウント
    elif s[i] == s[i+1]:
        cnt+=1
    #違うなら納めてカウント戻す
    else:
        s_comp.append(str(s[i])*cnt)
        cnt = 1

#出力計算
out = 0
cnt = 0

for i in range(1,len(s_comp),2):
    cnt+=1
    #指定回数以上行った場合ブレイク
    if cnt > k:
        break
    if s_comp[i][0] == "R":
        s_comp[i] = "L"*len(s_comp[i])
    elif s_comp[i][0] == "L":
        s_comp[i] = "R"*len(s_comp[i])
    

#合体
s = ""
for i in range(len(s_comp)):
    s += str(s_comp[i])

#数える
cnt = 0
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,k = inpl()
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()

now = S[0]
change = 1
for i in range(1, len(S)):
    if now != S[i]:
        change += 1
    now = S[i]

if change == 1 or change == 2 or (change-2) <= K:
    print(N - 1)
else:
    print(min(N - 1, N - change + 2 * K))

Submission status: Accepted

Solution code:
"""別解
解説動画でやってること。

考察問題。

ランレングス法みたいな考え方をする。

LグループとRグループに分けて考える。

LグループとRグループの境目を選択して操作をすると、基本的に幸福な人の数を＋２できる

ただし、端っこの境目を選んだときのみ、＋１になる。


・入力例２を考える

## 初期状態
 L R R L R L R R L R L L R
   .         .         .     幸福な人：3人


## LグループとRグループの境目を選択して、操作をする

 L R R L R L R R L R L L R
  |___|

 L L L L R L R R L R L L R
   . . .     .         .     幸福な人：5人

## LグループとRグループの境目を選択して、操作をする

 L L L L R L R R L R L L R
        |_|

 L L L L L L R R L R L L R
   . . . . . .         .     幸福な人：7人

## LグループとRグループの境目を選択して、操作をする

 L L L L L L R R L R L L R
            |___|

 L L L L L L L L L R L L R
   . . . . . . . .     .     幸福な人：9人

## LグループとRグループの境目を選択して、操作をする

 L L L L L L L L L R L L R
                  |_|

 L L L L L L L L L L L L R
   . . . . . . . . . . .     幸福な人：11人

## LグループとRグループの境目を選択して、操作をする

 L L L L L L L L L L L L R
                        |_|

 L L L L L L L L L L L L L
   . . . . . . . . . . . .   幸福な人：12人


この考察からすると、初期状態の幸福な人の数を score とすると、

・K回操作して、初期状態の幸福な人に加えて 2*K 人を幸福にすることができたパターン = score + 2*K
・K回以下の操作で、すべての人を L(R) にすることができたパターン = N-1

のどちらかなので、最終的な幸福な人の数 ans は、

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

となる。

初期状態の幸福な人の数 score をO(N)で数えればよいだけなので、計算量はO(N)

"""
def solve2():
    N, K = list(map(int, input().split()))
    S = input()

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

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


if __name__ == "__main__":
    solve2()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Nは人の数を表す
#Kは操作を行う回数を表す
N,K = map(int, input().split())
#SはLとRからなる文字列
S = list(input())
#点数を保管する変数
score = 0
ans = 0
#操作を行う前の点数を求めル
for i in range(N-1):
    if(S[i] == S[i+1]):
        score += 1
#操作を行うことによってスコアは＋2される(例外あり、ただし考える必要なし)        
ans = min(score+2*K,N-1)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

s = input()

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

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

Submission status: Accepted

Solution code:
def search_RL(S):
  amount=0
  for i in range(1,len(S)):
    if S[i-1]!=S[i]:
      amount+=1
  return amount

N,K=map(int,input().split())
S=input()
sum_RL=search_RL(S)
if -(-sum_RL//2) >= K:
  if (len(S)-sum_RL-1+2*K) >len(S)-1:
    print(len(S)-1)
  else:
    print(len(S)-sum_RL-1+2*K)
else:
  if (len(S)-sum_RL-1+2*K) >len(S)-1:
    print(len(S)-1)
  else:
    print(len(S)-sum_RL+2*K+1)

Submission status: Accepted

Solution code:
#

def happiness(s):
    h = 0
    c = s[0]
    for i in range(1,len(s)):
        if s[i] == c:
            h = h + 1
        else:
            c = s[i]
    return h

def schrun(s,l):
    c = s[l]
    i = l+1
    while (i<len(s)) and (s[i] == c) :
        i = i+1
    return i
        
#
n, k = map(int, input().split())
s = input()
#
h = happiness(s)
i = 0
l = 0
while( (i<k) and (l<n) and (h<n-1)):
    l = schrun(s,l)
    r = schrun(s,l)-1
    if r == n-1:
        h = h + 1
    else:
        h = h + 2
    i = i + 1
    l = r + 1

print(h)

Submission status: Accepted

Solution code:

nk = list(map(int, input().split()))
n = int(nk[0])
k = int(nk[1])
s = list(input())

ans = 0
l = 0
r = 0

for i in range(n-1):
    if s[i] == s[i+1]:
        ans += 1
    elif s[i] == ('R'):
        r += 1
    else :
        l += 1

ans += min(k,max(l,r)) + min(k,l,r)

print(ans)

Submission status: Accepted

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

    happiness = 0
    for i in range(n-1):
        if s[i:i+2] in ['LL', 'RR']:
            happiness += 1
    
    ope = 0
    while ope < k:
        happiness += 2
        ope += 1
    print(min(n-1, happiness))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, k = li()
s = ns()

# 幸福度の初期値
ans = 0
for si, sj in zip(s[:-1], s[1:]):
    if si == sj:
        ans += 1

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

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()

def splitter(type,input):
    return list(map(lambda x:type(x),input.split()))


ss1 = splitter(int,s1)

N = ss1[0]
K = ss1[1]
S = s2

d = {"M":0,"R":1,"L":-1}
def h(str):
    happy = 0

    a = "M" + str + "M"
    for i in range(len(a)):
        happy += (1 if (a[i] == a[i+d[a[i]]]) else 0)
    happy -= 2
    return happy

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

Submission status: Accepted

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


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

    comp = [0]
    for pre, curr in zip(S[0]+S, S):
        if pre == curr:
            comp[-1] += 1
        else:
            comp.append(1)

    print(sum(comp)-max(len(comp)-2*K, 1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
nk = input().split(" ");
n = int(nk[0]);
k = int(nk[1]);
s = input();

hukou = 0;
for i in range(n-1) :
	if s[i] == 'R' and s[i+1] == 'L' :
		hukou += 2;

edge = 0;
if s[0] == 'L' :
	edge += 1;
if s[n-1] == 'R' :
	edge += 1;

while hukou > 0 and k > 0 :
	hukou -= 2;
	k -= 1;

while edge > 1 and k > 0 :
	edge -= 1;
	k -= 1;

ans = n-edge-hukou;
if ans > n-1 :
	ans = n-1

print(ans);

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

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

Submission status: Accepted

Solution code:
import sys
import re
n, k = map(int, sys.stdin.readline().split())
S = sys.stdin.readline()

ptnr = 'R+'
ptnr = re.compile(ptnr)
ptnl = 'L+'
ptnl = re.compile(ptnl)

if len(ptnl.findall(S)) <=len(ptnr.findall(S)):
    f = 'L'
else:
    f = 'R'

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

idx = []
for i in range(n):
    if S[i] == f:
        idx.append(i)
idx.append(-10)

s =-1
e =-1
ten = [0]
for i in range(len(idx)-1):
    if s ==-1:
        s = idx[i]
    if idx[i]+1 != idx[i+1]:
        e = idx[i]
        if s==0 and e ==n-1:
            pass
        elif s ==-1 or e==-1:
            pass
        elif s ==0 or e ==n-1:
            ten.append(1)
        else:
            ten.append(2)
        s =-1
ten = sorted(ten, reverse=True)
print(score+ sum(ten[0:k]))

Submission status: Accepted

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