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:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,K = LMIIS()
    S = input()
    people = [0]
    

    count = 0
    pre = S[0]
    for c in S:
        if pre == c:
            count += 1
        else:
            pre = c
            people.append(count)
            count = 1
    people.append(count)
    
    while len(people) > 2 and K > 0:
        fusion = people[-1] + people[-2] + people[-3]
        for _ in range(3):
            people.pop()
        people.append(fusion)
        K -= 1
    print(sum(people)-len(people)+people.count(0))
        



        
            






if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
  n, k = map(int, input().strip().split())
  s = input().strip()
  score = 0
  for i in range(n-1):
    if s[i:i+2] in ['LL', 'RR']:
      score += 1
  print(min(score + 2*k, n-1))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys

n, k = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

def main():
    cnt_seq = 1
    for i in range(n-1):
        if s[i] != s[i+1]:
            cnt_seq += 1
    
    res = n - cnt_seq
    r = k
    the_other = dict([('L', 'R'), ('R', 'L')])
    a = s[0]
    b = the_other[a]
    for i in range(1, n):
        if not r:
            break
        if s[i] == a and s[i-1] == b:
            res += 2
            r -= 1
    if s[-1] == b and r:
        res += 1

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

RL=0
LR=0
unhappy=0

for i in range(0,N):
    if S[i]=='R' and S[i+1]=='L':
        RL+=1
    elif S[i]=='L' and S[i+1]=='R':
        LR+=1

if S[0]=='L' and S[N-1]=='L':
    if K>=RL:
        print(N-1)
    else:
        RL-=K
        print(N-2*RL-1)
elif S[0]=='R' and S[N-1]=='R':
    if K>=RL:
        print(N-1)
    else:
        RL-=K
        print(N-2*RL-1)
elif S[0]=='L' and S[N-1]=='R':
    if K>RL:
        print(N-1)
    elif K==RL:
        print(N-2)
    else:
        RL-=K
        print(N-2*RL-2)
else:
    if K>RL:
        print(N-1)
    elif K==RL:
        print(N-1)
    elif K==RL-1:
        print(N-2)
    else:
        RL-=K
        print(N-2*RL)

Submission status: Accepted

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

Submission status: Accepted

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

how_many=[]
LR=[]
 
counter=0
for i in range(1,n):
    counter+=1
    if s[i-1]!=s[i]:
        how_many.append(counter)
        LR.append(s[i-1])
        counter=0
how_many.append(counter+1)
LR.append(s[-1])

accumulate=[0]
for i in range(len(how_many)):
    accumulate.append(accumulate[-1]+how_many[i])


ans=0
max_left=0
max_right=0
for g in range(len(LR)):
    l=g
    if LR[l]=="L":
        r=min(g+2*k,len(LR))
    else:
        r=min(g+2*k+1,len(LR))
    if ans<=accumulate[r]-accumulate[l]:
        ans=accumulate[r]-accumulate[l]
        max_left=l
        max_right=r
remain=how_many[:max_left]+how_many[max_right:]
ans1=ans-1+sum(remain)-len(remain)


ans=0
max_left=0
max_right=0
for g in range(len(LR)):
    l=g
    if LR[l]=="R":
        r=min(g+2*k,len(LR))
    else:
        r=min(g+2*k+1,len(LR))
    if ans<=accumulate[r]-accumulate[l]:
        ans=accumulate[r]-accumulate[l]
        max_left=l
        max_right=r

remain=how_many[:max_left]+how_many[max_right:]
ans2=ans-1+sum(remain)-len(remain)
print(max(ans1,ans2))

Submission status: Accepted

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

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

Submission status: Accepted

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

not_happy = 0
R = 0
R_edge = 0

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

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

#print(R)
#print(R_edge)

if K <= R:
    R -= K
else:
    R = 0
    R_edge = 1

not_happy = R*2 + R_edge
happy = N - not_happy

#print(R)
#print(R_edge)
#print(not_happy)
print(happy)

Submission status: Accepted

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

score = 0

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N, K = Scanner.map_int()
    S = Scanner.string()
    cnt = 0
    for i in range(N):
        if S[i] == "R":
            if i + 1 < N and S[i+1] == "R":
                cnt += 1
        else:
            if i - 1 >= 0 and S[i-1] == "L":
                cnt += 1
    print(min(N-1, cnt + 2 * K))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  s=input()  
  B=s.count('RL')+s.count('LR')+1
  print(min(n-1,n-B+2*k))  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  s=input()
  
  A=(('L','R'),('R','L'))
  B=[]
  Bappend=B.append
  cnt=0
  for i in range(n-1):
    tmp=(s[i],s[i+1])
    cnt+=1
    if tmp==A[0]:
      Bappend(cnt)
      cnt=0
    elif tmp==A[1]:
      Bappend(cnt)
      cnt=0
  cnt+=1
  Bappend(cnt)
  print(n-max(1,len(B)-2*k))
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  s=input()
  
  A=(('L','L'),('L','R'),('R','L'),('R','R'))
  B=[]
  cnt=0
  for i in range(n-1):
    tmp=(s[i],s[i+1])
    cnt+=1
    if tmp==A[1]:
      B.append(cnt)
      cnt=0
    elif tmp==A[2]:
      B.append(cnt)
      cnt=0
  cnt+=1
  B.append(cnt)
  if len(B)//2<=k:
    unhappy=1
  else:
    unhappy=len(B)-2*k
   
  print(n-unhappy)
  
if __name__=='__main__':
  main()

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    s = str(input())
    
    count = 0
    change = 0
    for i in range(N-1):
        if s[i+1] == s[i]:
            count += 1
        else:
            change += 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

u = int(s[0] == 'L') + 2 * s.count('RL') + int(s[-1] == 'R')
print(min(n - u + 2 * k, n - 1))

Submission status: Accepted

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

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

if k < paired:
    print(score + 2 * k)
else:
    print(n - 1)

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

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

if S[0]=="L":
    key="R"
    not_key="L"
else:
    key="L"
    not_key="R"

flag=False
count=0
for i in range(1,N):
    if count==K:
        break
    if S[i]==key:
        if flag==False:
            flag=True
            S[i]=not_key
        elif flag==True:
            S[i]=not_key
    elif S[i]==not_key:
        if flag==True:
            count+=1
            flag=False

L_flag=False
R_flag=False
count=0
for i in range(N):
    if S[i]=="L":
        if L_flag==False:
            L_flag=True
            R_flag=False
        elif L_flag==True:
            count+=1

    elif S[i]=="R":
        if R_flag==False:
            R_flag=True
            L_flag=False
        elif R_flag==True:
            count+=1

print(count)

Submission status: Accepted

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

num = 0
for index in range(len(S)-1):
    if S[index] == 'L' and S[index+1] == 'L':
        num = num + 1
    if S[index] == 'R' and S[index+1] == 'R':
        num = num + 1

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

print(result)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
RLE = []
now_char = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == now_char:
        cnt += 1
    else:
        RLE.append([now_char, cnt])
        now_char = S[i]
        cnt = 1
RLE.append([now_char, cnt])

n = len(RLE)
if n//2 <= K:
    print(N-1)
    exit()
print(N - n + 2 * K)

Submission status: Accepted

Solution code:
def runlength(S):
    cnt = 1
    res = []
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            cnt += 1
        else:
            res.append(cnt)
            cnt = 1

    res.append(cnt)
    return res


def main():
    N, K = map(int, input().split())
    S = input()
    A = runlength(S)
    ans = 0
    for a in A:
        a -= 1
        ans += a
    ans = min(N-1, ans + 2 * K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
S = list(sr())
start = 0
for i in range(1, N):
    if S[i] == S[i-1]:
        start += 1

answer = min(start + 2 * K, N-1)
print(answer)
# 45

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
S = input()
if N == 1:
    print(0)
else:
    lc = max(S.count('L')-1,0)
    rc = max(N-lc-1,0)
    maxc = lc+rc
    nowc = 0
    now = S[0]
    for i in range(1,N):
        if S[i] == now:
            nowc += 1
        else:
            now = S[i]
    print(min(nowc+2*K,maxc))

Submission status: Accepted

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

Submission status: Accepted

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

ans = N
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())
ans = l = 0
for i in input():
    ans += (n==i)
    n = i
    l += 1
print(min(ans+2*k, l-1))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:


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

L = []

tmp = None
cnt = 0
for s in S:
  if tmp == None:
    tmp = s
    cnt = 1
  else:
    if tmp != s:
      L.append((cnt, tmp))
      cnt = 1
      tmp = s
    else:
      cnt += 1
else:
  L.append((cnt, tmp))


ll = len(L)
 
for i in range(K):
  if ll == 1:
    break
  if ll == 2:
    ll -= 1
  else:
    ll -= 2

print(N - ll)

Submission status: Accepted

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

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

two = 0
pre = s[0]
cont = 1
ans = 0
for c in s[1:]:
    if c != pre:
        if c == s[0]:
            two += 1
        ans += cont - 1
        cont = 1
        pre = c
    else:
        cont += 1
ans += cont - 1

if s[0] != s[-1] and k > two:
    ans += 1
print(ans + 2 * min(k, two))

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    S = 'R' + S + 'L'
    a = S[0]
    b = S[1]
    s = 0
    for c in S[2:]:
        if c == 'R' and b == 'R':
            s += 1
        if b == 'L' and a == 'L':
            s += 1
        a = b
        b = c
    print(min(N-1, s + 2 * K))
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
c = 0

pre = ''
for s in S:
    if s == 'L':
        if pre == 'L':
            ans += 1
        else:
            pre = s
            c += 1
    else:
        if pre == 'R':
            ans += 1
        else:
            pre = s

cc = 0
if S[0] == 'L':
    cc += 1
if S[-1] == 'R':
    cc += 1

if c <= K:
    ans += 2 * c
    K -= c
    c = 0
else:
    ans += 2 * K
    c -= K
    K = 0

print(min(ans, N - 1))

Submission status: Accepted

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

Submission status: Accepted

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

x = 0
for i in range(N):
  if (S[i]=="L" and 0<i and S[i-1]=="L" or
      S[i]=="R" and i<N-1 and S[i+1]=="R"):
    x += 1
print min(x+2*K, N-1)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

happy = n
for i in range(n - 1):
    if s[i] + s[i + 1] == "RL":
        happy -= 2
if s[0] == "L":
    happy -= 1
if s[-1] == "R":
    happy -= 1

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

Submission status: Accepted

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

h = 0
for a, b in zip(s, s[1:]):
    if a == b:
        h += 1
h += 2 * k

print(min(n-1, h))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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


X = min(len([s for s in S.split('L') if s != '']), len([s for s in S.split('R') if s != '']))
ans += min(X, K) * 2
print(min(ans, N - 1))

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
  else:
    if s[i]==s[0] and k>0:
      if s[0] in s[i+1:]:
        h+=2
        k-=1
      else:
        h+=1
        k-=1
print(h)

Submission status: Accepted

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

s = list(s)

li = []
que = []
for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(i)
li.append(n-1)
if len(li) == 1:
    print(n-1)
    exit()

for i in range(0,len(li)-1, 2):
    if k > 0:
        char = s[li[i]]
        a = s[li[i]+1:li[i+1]+1]
        s[li[i]+1:li[i+1]+1] = char * (li[i+1] - li[i])
    k -= 1

happiness = 0

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

print(happiness)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,K=map(int,input().split())
S=input()
if N==1:
    print(0)
    exit()

_K=K
_S=list(S)

pre=_S[0]
flag=0
for i in range(1,N):

        if (_K>0 or flag==1 )and pre!=_S[i]:
            flag=1
            _S[i]=pre
        elif pre==_S[i] and flag==1:
            _K-=1
            flag=0

count=0
if _S[0]=="R" and _S[1]=="R":
    count+=1
if _S[-1]=="L" and _S[-2]=="L":
    count+=1

for i in range(1,N-1):
    if _S[i-1]=="L" and _S[i]=="L"  or _S[i]=="R" and _S[i+1]=="R":
        count+=1

print(count)

Submission status: Accepted

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

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


X = (len([s for s in S.split('L') if s != '']) + len([s for s in S.split('R') if s != '']))
ans += min(X, K) * 2
print(min(ans, N - 1))

Submission status: Accepted

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

R = []
tmp = None
for i in range(N):
  if tmp == None:
    tmp = (1, S[i])
  else:
    if S[i] == tmp[1]:
      tmp = (tmp[0]+1, S[i])
    else:
      R.append(tmp)
      tmp = (1, S[i])
else:
  R.append(tmp)

len_r = len(R)
for k in range(K):
  if len_r >= 3:
    len_r -= 2
  elif len_r == 2:
    len_r -= 1
  else:
    break
print(N - len_r)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
e=(S[0]=='L')+(S[-1]=='R')
i=S.count("RL")
c=max(i-K,0)*2+max(e-max(K-i,0),0)

print(N-max(c,1))

Submission status: Accepted

Solution code:
N, K=map(int, input().split())
S=input()
A=[]
tmp=1
for i in range(1,N):
    if S[i-1]==S[i]:
        tmp+=1
    else:
        A.append(tmp)
        tmp=1
A.append(tmp)
 
ans=sum(A)-len(A)+(K)*2
 
if ans<N-1:
    print(ans)
else: print(N-1)

Submission status: Accepted

Solution code:
import itertools

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

gnum = 0
for key, elems in itertools.groupby(S):
    gnum += 1

k = K
while gnum > 1 and K > 0:
    if gnum != 2:
        gnum -= 2
    else:
        gnum -= 1
    K -= 1

if gnum == 1:
    print(N - 1)
else:
    print(N - gnum)

Submission status: Accepted

Solution code:
nk=list(map(int,input().split()))
s=input()
L=[]
R=[]
lr="a"
for i in range(nk[0]):
    if lr=="L":
        if s[i]=="R":
            lr="R"
            R.append(1)
        else:
            L[-1]+=1
    elif lr=="R":
        if s[i]=="L":
            lr="L"
            L.append(1)
        else:
            R[-1]+=1
    else:
        lr=s[0]
        if lr=="L":
            L.append(1)
        else:
            R.append(1)
L.sort(reverse=True)
R.sort(reverse=True)
lsum=sum(L[:nk[1]])
rsum=sum(R[:nk[1]])
if len(L)<=nk[1] or len(R)<=nk[1]:
    print(nk[0]-1)
else:
    if lsum+sum(R)>rsum+sum(L):
        rmerge=sum(R[:nk[1]+1])+lsum
        R=R[nk[1]:]
        if R!=[]:
            R[0]=rmerge
        else:
            R=[rmerge]
        L=L[nk[1]:]
        ans=sum(R)-len(R)+sum(L)-len(L)
    else:
        lmerge=sum(L[:nk[1]+1])+rsum
        L=L[nk[1]:]
        if L!=[]:
            L[0]=lmerge
        else:
            L=[lmerge]
        R=R[nk[1]:]
        ans=sum(L)-len(L)+sum(R)-len(R)
    print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
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)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    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))
    return

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
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)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    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))
    return

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import numpy as np
N, K = map(int,input().split())
s = input()
res = 0
if s[0] == 'R' and s[1] == 'R':
    res += 1
for i in range(1,N-1):
    if s[i-1] == 'R' and s[i] == 'L':
        continue
    elif s[i+1] == 'L' and s[i] == 'R':
        continue
    res += 1
if s[N-1] == 'L' and s[N-2] == 'L':
    res += 1
res = min([N-1, res+2*K])
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0

i = 1
while i < len(s):
    if cnt == k:
        break

    if s[i] != s[i-1]:
        cnt += 1
        start = i
        target = s[i]

        while  i < len(s) and target == s[i]:
            if s[i] == 'R': s[i] = 'L'
            else: s[i] = 'R'

            i += 1   

        continue    

    i += 1

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

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
x=s.count('RL')
y=0
cnt=0
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
if s[0]=='L' and s[n-1]=='R':
  y+=1
while k>0:
  if x>0:
    x-=1
    cnt+=2
    k-=1
  else:
    if y>0:
      cnt+=1
      y-=1
      k-=1
    else:
      break
print(min(n-1,cnt))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc140/tasks/abc140_d

# 性質ちゃんと考える
# 連長圧縮したあとならば、r-lが奇数である組み合わせをひっくり返すのに価値がある
# 反転しても中の幸福度は変化しない。
# 幸福度が改善するのはLR or RLでなくなった部分だけ

# LLLLLL (幸福度5(max))
# LRLRRL (幸福度1 (4人死んでるので)) #一回の操作が最善ならば必ず2人改善する(l==rの場合は1人改善)
# LLRLLL (幸福度3 (1から2人復活したので))


# もしラストをひっくり返すことで幸福度が上がるなら？
# ラストに0文字のLをfillする必要がある？
# LRRLRLRRLRLLR (max 12) (N-1) (今は3)
# 3回操作によって＋6なので9となる

# 10 1
# LLLLLRRRRR (max9) (いま8)
# そうかL→RとR→Lの個数をカウントすればいいんだ

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

score = -1
LtoR = 0
RtoL = 0
pre = S[0]
for s in S:
    if pre == s:
        score += 1
    elif pre == 'L':
        LtoR += 1
    elif pre == 'R':
        RtoL += 1
    else:
        raise ValueError('something wrong')
    pre = s

# print(score, LtoR, RtoL)
if K <= min(LtoR, RtoL):
    print(score + 2 * K)
else:
    print(score + LtoR + RtoL)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, k = na()
s = ns()
c = 0
for key, val in itertools.groupby(s):
    c += len(list(val)) - 1
ans = min(c + 2*k, n-1)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from itertools import groupby

N,K = map(int,input().split())
S = input()
gnum = len(list(groupby(S)))
if gnum<=2*K-1:
  print(N-1)
else:
  print(min(N-(gnum-2*K),N-1))

Submission status: Accepted

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

ch = 0
ans = 0

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

print(ans+min(K*2,ch))

Submission status: Accepted

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

N,K=map(int,input().split())
S=input().strip()
cnt1=0
for i in range(1,N):
    if S[i]!=S[i-1]:
        cnt1+=1
num=[]
cnt=0
for i in range(1,N):
    if S[i]==S[i-1]:
        cnt+=1
    else:
        num.append(cnt)
        cnt=0
#print(num,cnt)
num.append(cnt)
if cnt1>=2*K:
    ans=sum(num)+2*K
    print(ans)
else:
    print(N-1)

"""

print(num)
if len(num)<=2*K+1:
    ans=sum(num)
else:
    cost=sum(num[:2*K+1])
    ans=cost
    for i in range(len(num)-(2*K+1)):
        cost+=num[2*K+1+i]-num[i]
        ans=max(ans,cost)
print(ans-1)"""

Submission status: Accepted

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

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