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:
# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

n, k = [int(i) for i in input().split()]
s = input()

ans = 0
lblocks = 0
# if s[0] == "L":
#     lblocks += 1
flag = False
if s[0] == "L":
    flag = True
for i,v in enumerate(s):
    if i == 0:
        continue
    if s[i] == s[i-1]:
        ans += 1
    if s[i] == "L":
        if not flag:
            lblocks += 1
            flag = True
    else:
        flag = False
if lblocks == 0:
    print(n-1)
else:
    if lblocks < k:
        print(n-1)
    else:
        print(ans+k+k)

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(n-1-max((count-2*k),0))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
s_num = []
point = 1
prev = s[0]
ans = 0
for i in range(n - 1):
    if prev != s[i + 1]:
        prev = s[i + 1]
        s_num.append(point)
        ans += point - 1
        point = 1        
    else:
        point += 1
s_num.append(point)
ans += point - 1
kkk = max(len(s_num) - 2, 0)
ans = ans + min(kkk, k) * 2
if kkk < k:
    ans += k - kkk
ans = min(n - 1, ans)
print(ans)

Submission status: Accepted

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

S = input()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
cnt = 1
li = []
for i in range(n-1):
    if s[i] == s[i+1] and s[i] == "R":
        cnt += 1
    elif s[i] == s[i+1] and s[i] == "L":
        cnt += 1
    else:
        li.append((s[i], cnt))
        cnt = 1
if n > 1:
   li.append((s[i], cnt))
cut = len(li) - 1

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

Submission status: Accepted

Solution code:
N, K = list(map(int,input().split()))
S = input()
S = list(S)
counter = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        counter += 1

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

Submission status: Accepted

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

prev = None
num_regions = 0
score = 0
for c in S:
  if c != prev:
    num_regions += 1
  else:
    score += 1
  prev = c

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

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate

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

l = [len(list(g)) for k, g in groupby(S)]
# print(l)
m = min(len(l)//2, K)
# print(m)
a = [0]*(N+1)
x = 0
for l_i in l[:m]:
    x += l_i
    a[x] += 1
x = N
for l_i in l[-m:][::-1]:
    x -= l_i
    if a[x] == 0:
        a[x] -= 1

# print(list(accumulate(a))[:-1])

s_list = list(S)
for i, b in enumerate(list(accumulate(a))[:-1]):
    if b%2:
        s_list[i] = "R" if S[i] == "L" else "L"

# print(s_list)

count = 0
for i, s_i in enumerate(s_list):
    if s_i == "L":
        if i == 0:
            continue
        count += s_list[i-1] == "L"
    else:
        if i == N-1:
            continue
        count += s_list[i+1] == "R"

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N, K = _li()
S = _s()

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

ans = N - (lr + rl + 1)
cand = min(lr, rl)
ans += 2 * min(cand, K)
if K > cand:
    if lr > rl and (S[0] == 'L' or S[-1] == 'R'):
        ans += 1
    elif lr < rl and (S[0] == 'R' or S[-1] == 'L'):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#D問題
import math

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

pr = []
NL = 0
NR = 0
for i in range(N):
    s = S[i]
    if i == 0:
        if s == "L":
            NL+=1
        else:
            NR+=1
    elif s == "L":
        if NL > 0:
            NL+=1
        else:
            pr.append(NR)
            NL = 1
            NR = 0
    else:
        if NR > 0:
            NR+=1
        else:
            pr.append(NL)
            NR = 1
            NL = 0

if NL > 0:
    pr.append(NL)
if NR > 0:
    pr.append(NR)
    
LP = len(pr)
ans = sum(pr)-max((LP-2*K),1)
#print(pr)
print(ans)

Submission status: Accepted

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

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

a=score+K*2
b=len(S)-1
print(min(a,b))

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    ls = list(input())
    now = ls[0]
    same = 0
    dif = 0
    for i in range(1,n):
        if now == ls[i]:
            same += 1
        else:
            dif += 1
        now = ls[i]
    ans = same + min(dif,k*2)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

mn=0
mt=False

pre='N'
now=0
for i, val in enumerate(s):
    if val == pre:
        now+=1
    if i != 0:
        if pre != val:
            mn+=1
    pre=val

c2=mn//2
if k > c2:
    k-=c2
    now+=(c2*2)
else:
    now+=(k*2)
    k=0

if k > 0 and mn%2 ==1:
    now+=1
print(now)

Submission status: Accepted

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

m = []

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

m.append(cnt)

sums = []

ans = 0

l = 0
r = 0
turn = 0

sums.append(0)
for i in range(len(m)):
    sums.append(sums[i] + m[i])

if(2*k + 1 >= len(m)):
    ans = n - 1
else:
    for i in range(len(m) - (2 * k + 1)):
        ansi = 0
        ansi += sums[i] - sums[0] - i
        ansi += sums[len(m)] - sums[i+2*k+1] - (len(m) - (2 * k + 1))
        ansi += sums[i+2*k+1] - sums[i] - 1
        ans = max(ans, ansi)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
import numpy as np
S = np.array(list(input()))
count = 0
if len(S) >= 2:
    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] == 'R' and S[i+1] == 'R':
        count += 1
    if S[i] == 'L' and S[i-1] == 'L':
        count += 1
count += K * 2
print(min(count, N-1))

Submission status: Accepted

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

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

ans = 0
if s[0] == "R" and s[1] == "R":
    ans += 1
if s[n-1] == "L" and s[n-2] == "L":
    ans += 1

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

if s[n-1] != s[n-2]:
    hanten += 1

if k <= hanten // 2:
    print(ans + k*2)
else:
    print(ans + hanten)

Submission status: Accepted

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

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

for i in range(k):
    count += min(block, 2)
    block -= 2
    if block <= 0:
        break

print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[0 if c=='L' else 1 for c in input()]
x=S[0]
f=0
r=0
p=-1
for i in range(N):
    if f==0 and S[i]!=x:
        f=1
    if S[i]!=x:
        if K>0:
            S[i]=x
    elif f==1:
        K-=1
        f=0
    if S[i]==p:
        r+=1
    p=S[i]
print(r)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
count  = point = 0
while(count < n - 1):
	if (s[count] == s[count + 1]):
		point += 1
	count += 1
point += 2 * k
if (point > n - 1):
	print(n - 1)
else:
	print(point)

Submission status: Accepted

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

cnt = 0
temp1 = ""
btn = 0
ans = 0

for i in range(n):
    if i == 0:
        temp = s[i]
        continue
    if temp == s[i]:
        ans += 1
        continue
    else:
        temp = s[i]
        btn += 1
        if btn == 2:
            cnt += 1
            btn = 0

if cnt >= k:
    print(ans+2*k)
else:
    if btn == 1:
        print(ans+2*cnt+1)
    else:
        print(ans+2*cnt)

Submission status: Accepted

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

info = [1]
cur = S[0]

for i in range(1,N):
    if S[i] == cur:
        info[-1] += 1
    else:
        info.append(1)
        cur = S[i]

if K * 2 + 1 >= len(info):
    print(N-1)
else:
    print(sum(info) - (len(info)-(2 * K + 1)) - 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
c = 0
lr = 0
rl = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    c += 1
  elif s[i] == 'L':
    lr += 1
  else:
    rl += 1
if k > min(lr,rl):
  if lr == rl:
    print(c+2*lr)
  else:
    print(c+min(lr,rl)*2+1)
else:
  print(c+2*k)

Submission status: Accepted

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

s=input()
now=s[0]

L=[0]
for c in s:
    if c==now:
        L[-1]+=1
    else:
        now=c
        L.append(1)
"""
zen_max=max(L)
cen_max=max(L[1:-1])
ans=zen_max
if zen_max != cen_max:
    ans-=1
"""

ans=sum(L)-len(L)

choice=len(L)//2

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
LR = 0
RL = 0
RR = 0
LL = 0
for i in range(n-1):
  if s[i]=='L' and s[i+1]=='R':
    LR += 1
for i in range(n-1):
  if s[i]=='R' and s[i+1]=='L':
    RL += 1
for i in range(n-1):
  if s[i]=='R' and s[i+1]=='R':
    RR += 1
for i in range(n-1):
  if s[i]=='L' and s[i+1]=='L':
    LL += 1
ans = RR + LL
m = min(LR,RL)
M = max(LR,RL)
if k < m:
  ans += 2*k
else:
  ans += 2*m
  if k < M:
    ans += k-m
  else:
    ans += M-m
print(ans)

Submission status: Accepted

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

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

S = N-1 - B

if 2*K>=B:
  Sm = N-1
else:
  Sm = S+2*K
  
print(Sm)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
s = input()
li = [0] * n
ans = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        ans += 1
    else:
        li[i + 1] += 1
    li[i + 1] += li[i]
for i in range(n):
    li[i] //= 2
ans += 2 * min(li[-1], k)
if s[0] != s[-1] and li[-1] < k:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, k = LI()
s = S()
cnt = 0
if s[0] == 'L':
    cnt += 1
if s[-1] == 'R':
    cnt += 1
for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L':
        cnt += 2



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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
c = s[0]
con = 1
odd = []
even = []
now = 1
ans = 0

for i in range(1, n):
    if s[i] == c:
        con += 1
    else:
        c = s[i]
        if not con == 1:
            ans += con - 1
        if now == 1:
            odd += [con]
            now = 2
        elif now == 2:
            even += [con]
            now = 1
        con = 1
else:
    if not con == 1:
        ans += con - 1
    if now == 1:
        odd += [con]
    elif now == 2:
        even += [con]

odd_l = len(odd)
even_l = len(even)
length = min(odd_l, even_l)
if k >= length:
    print(n-1)
else:
    print(ans + k * 2)

Submission status: Accepted

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

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

if len(S) == 1:
    print(0)
    exit()
ans = 0
if S[0] == 'R' and S[1] == 'R':
    ans += 1
if S[-1] == 'L' and S[-2] == 'L':
    ans += 1
for i in range(1, N-1):
    if S[i] == 'L' and S[i-1] == 'L':
        ans += 1
    elif S[i] == 'R' and S[i+1] == 'R':
        ans += 1

ans += 2 * K

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

Submission status: Accepted

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

Submission status: Accepted

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

count1 = 0
for i in range(n):
    if i == 0 or (i >= 1 and s[i] == s[i - 1]):
        count1 = count1 + 1
    else:
        snumbers.append(count1)
        count1 = 1
snumbers.append(count1)

happier = 0
for i in snumbers:
    happier = happier + i - 1

for i in range(min(k, len(snumbers) // 2)):
    happier = happier + 2

print(min(n - 1, happier))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

N, K = getlist()
S = list(input())

L = []
v = S[0]
c = 0
for i in range(N):
	if S[i] == v:
		c += 1
	else:
		L.append(c)
		c = 1
	v = S[i]

L.append(c)

ans = 0
for i in L:
	ans += i - 1

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

Submission status: Accepted

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


def main(n, k, a):
    total = sum(a)
    return total + min(2*k, n-total-1)


if __name__ == "__main__":
    n, k = map(int, input().split())
    s = input()
    a = []
    for i in range(n-1):
        if s[i] == s[i+1]:
            a.append(1)
        else:
            a.append(0)

    print(main(n, k, a))