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: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
S = [1 if x=='R' else -1 for x in input()]

for i in range(K):
    l = -1
    prev = S[0]
    for j in range(1, N):
        current = S[j]
        if current != prev:
            l = j
            break
        prev = current
    if l == -1:
        break

    r = N - 1
    prev = S[l]
    for j in range(l+1, N):
        current = S[j]
        if current != prev:
            r = j - 1
            break
        prev = current
    left = S[:l]
    target = S[l:r+1]
    right = S[r+1:]
    target.reverse
    target = [-x for x in target]
    S = left + target + right

S.insert(0, 1)
S.append(-1)
ans = 0
for i in range(N):
    x = S[i+1]
    y = S[i+1+x]
    if x == y:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


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

left = 0
right = n - 1


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

    else:
        break

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

    for i in range(left, right):
        s[i] *= -1

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

print(n - tmp - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import re
n, k = [int(i) for i in sys.stdin.readline().split()]
s = input()
s_origi = copy.deepcopy(s)
def _reverse(text):
    res = text[::-1]
    res = ["R" if i == "L" else "L" for i in res]
    res = "".join(res)
    return res
for i in range(k):
    left = s.find("R")
    left = 0 if left == -1 else left
    right = s.rfind("R") + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
s = copy.deepcopy(s_origi)
for i in range(k):
    left = s.find("LR") + 1
    left = 0 if left == -1 else left
    right = s.rfind("RL") + 1
    if left > right:
        break

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = max(cnt, sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)]))
print(cnt)

Submission status: Time Limit Exceeded

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

l = -1
r = -1

for k in range(K):
    for i in range(1, N):
        if S[i] != S[i-1]:
            if l < 0:
                l = i
            else:
                r = i
                for s in range(l, r):
                    if S[s] == "L":
                        S[s] = "R"
                    else:
                        S[s] = "L"
                l = -1
                r = -1
                break
        elif i == N-1 and l >= 0:
            for s in range(l, N):
                if S[s] == "L":
                    S[s] = "R"
                else:
                    S[s] = "L"
            l = -1
            break
ans = 0
for i in range(1, N):
    if S[i] == S[i-1]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

final_ans = 0
if len(ans) == 2:
    print(n-1)
elif len(ans) == 1:
    print(n-1)
else:
    for i in range(k):
        b = max(ans[1:len(ans)-1])
        ind = ans[1:len(ans)-1].index(b)+1
    #    print(ind,b)
        if ind == 0:
            ans = [ans[ind]+ans[ind+1]] + ans[2:]
        elif ind == len(ans)-1:
            ans = ans[:len(ans)-2] + [ans[ind-1]+ans[ind]]
        else:
            ans = ans[:ind-1] + [ans[ind-1]+ans[ind]+ans[ind+1]] + ans[ind+2:]
  #      print(ans)
   # print(ans)
    
    for i in ans:
        final_ans += i-1
    print(final_ans)

Submission status: Time Limit Exceeded

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

for _ in range(0, k):
	l = 0
	r = 0
	p = s[0]

	for i in range(1, n):
		if p != s[i]:
			l = i
			break

	for i in range(l + 1, n):
		if p == s[i]:
			r = i
			break

	if l < r:
		for i in range(l, r):
			s[i] = p
	if r < l:
		for i in range(l, n):
			s[i] = p

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

print(c)

Submission status: Time Limit Exceeded

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

def solve():
    global K, S
    concat_S = S[:]
    while 'LL' in concat_S:
        concat_S = concat_S.replace('LL', 'L', 1)
    while 'RR' in concat_S:
        concat_S = concat_S.replace('RR', 'R', 1)

    ans = len(S) - len(concat_S)
    S = concat_S
    while K and len(S) > 3:
        S = ''.join([S[0], S[3:]])
        ans += 2
        K -= 1

    if K:
        if len(S) == 3:
            ans += 2
        elif len(S) == 2:
            ans += 1
        
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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


while k>0 and len(ls)>1:
  tmp = 0
  k-=1
  if len(ls) == 2:
    ls = [ls[0]+ls[1]]
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls = [tmp]+ls
  
print(n-len(ls))

Submission status: Time Limit Exceeded

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

def change(s,x):
  if s[x]=="L":
    s[x]="R"
  elif s[x]=="R":
    s[x]="L"

l=0
r=n-1    
 
while k >0 and 0<=l<n-1 and n-1>=r>0:
  if s[l]==s[l+1]:
    l += 1
  elif s[r]==s[r-1]:
    r -= 1
  elif l+1==r:
    for t in range(0,r):
      change(s,t)
    k-=1
  else:
    for t in range(l+1,r):
      change(s,t)
    k -= 1

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

print(h)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
S = [1 if x=='R' else -1 for x in input()]

for i in range(K):
    l = -1
    for j in range(1, N):
        if S[j] != S[j-1]:
            l = j
            break
    if l == -1:
        break

    r = N - 1
    for j in range(l, N-1):
        if S[j] != S[j+1]:
            r = j
            break
    
    temp = [-S[l + i] for i in range(r - l + 1)]
    temp.reverse()
    for i in range(r - l + 1):
        S[l + i] = temp[i]

S.insert(0, 1)
S.append(-1)
ans = 0
for i in range(N):
    x = S[i+1]
    y = S[i+1+x]
    if x == y:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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
while True:
  for i in range(k):
    if ans < n-2:
      ans += 2
    if ans == n-2:
      ans += 1
    else:
      break
print(ans)

Submission status: Time Limit Exceeded

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
        for j in range(0, i):
            ansi += m[j]-1
        for j in range(i+2*k+1, len(m)):
            ansi += m[j]-1
        ansi += sums[i+2*k+1] - sums[i] - 1
        ans = max(ans, ansi)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = list(input())
    base = S[0]
    flag = False
    for i in range(0, N):
        if K == 0:
            break
        if S[i] != base and (not flag):
            flag = True
            S[i] = base
        elif S[i] != base and flag:
            S[i] = base
        elif S[i] == base and flag:
            flag = False
            K -= 1
        else:
            pass
    
    ans = 0
    for i in range(N-1):
        ans += S[i] == S[i+1]
    
    print(ans)
  
if __name__ == "__main__":
    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] == S[i-1]:
        ans += 1

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,k = i_map()
    s = list(input())
    a = 0
    for i,q in itertools.groupby(s):
        # print(i,k)
        a += 1
    a -= 1
    print(n-1-max(a-2*k,0))




if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def read_str(): return sys.stdin.readline().strip()
def read_int(): return int(sys.stdin.readline().strip())
def read_ints(): return map(int, sys.stdin.readline().strip().split())
def read_str_split(): return list(sys.stdin.readline().strip())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))

def Main():
    n, k = read_ints()
    s = read_str()
    cnt = s.count('RL') + s.count('LR') + 1
    cnt = min(n-1, n-cnt+2*k)
    print(cnt)

if __name__ == '__main__':
    Main()

Submission status: Accepted

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

# In[1]:


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


# In[2]:


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


# In[ ]:

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  s=S()
  ans=0
  x=s[0]
  cnt=0
  for y in s[1:]:
    if x==y:
      cnt+=1
    else:
      ans+=cnt
      cnt=0
    x=y
  ans+=cnt

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

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#from decimal import Decimal
#mod = 1000000007
#mod = 998244353
#N = int(input())
N, K = map(int, input().split())
S = input()
#A = list(map(int, input().split()))
#flag = True
if N==1:
  print(0)
  exit()
cnt = 0
if S[0] == 'R':
  if S[1] == 'R':
    cnt += 1
if S[-1] == 'L':
  if S[-2] == 'L':
    cnt += 1
for k in range(1,N-1):
  if S[k] == 'L':
    if S[k-1] =='L':
      cnt += 1
  else:
    if S[k+1] == 'R':
      cnt += 1

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

print(ans)
#print('Yes')
#print('No')

Submission status: Accepted

Solution code:
import sys

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

ans = 0
split = 0
pre = S[0]
for i in range(1, N):
    if pre == S[i]:
        ans += 1
    else:
        split += 1
    pre = S[i]

# print(ans, split)
print(ans + min(2*K, split))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(input())
tmp = []
tmp.append(S[0])
for i in  range(1,N):
    if(S[i] != S[i-1]):
        tmp.append(S[i])
G = len(tmp)
G -= 2*K
G = max(G-1,0)

print(N-G-1)

Submission status: Accepted

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

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

lst.append(cnt)

ans=n-sum(lst)-1

lst2=[]
for i in lst:
    for j in range(i//2):
        lst2.append(2)
    
    if i%2==1:
        lst2.append(1)

lst3=[]
xxxxx=lst2.count(1)

if xxxxx%2==1:
    lst3.append(1)

for i in range(xxxxx//2):
    lst3.append(2)

for i in range(lst2.count(2)):
    lst3.append(2)

lst3.sort()
lst3.reverse()

if len(lst3)>k:
    ans+=sum(lst3[:k])
else:
    ans+=sum(lst3)


print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,K=mint()
S=input()
r1=0
r2=0
now=0
mark=S[0]
tmp=None
for i in range(N):
    if i<N-1 and S[i]==S[i+1]:
        now+=1
    if tmp==mark and S[i]!=mark:
        r2+=1
    tmp=S[i]
if tmp!=mark:
    r1+=1
    r2-=1
now+=2*min(K,r2)
K-=min(K,r2)
now+=min(K,r1)
print(now)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
Hap = 0
NewS = S[0]
def chan(X):
    if X == 'R':
        return 'L'
    else:
        return 'R'
for i in range(1,len(S)):
    strS = S[i]
    strS1 = S[i-1]
    if strS != strS1:
        NewS += strS
    else:
        Hap += 1
while len(NewS) > 1 and K != 0:
    Hap += 2
    NewS = chan(NewS[-1]) + NewS[2:-2] + chan(NewS[0]) 
    K -= 1
if Hap > N-1:
    Hap = N-1
print(Hap)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
r_cnt = 0
answer = 0
before = S[0]
for s in S:
  if s == before:
    answer += 1
  else:
    r_cnt += 1
    before = s
answer -= 1
if r_cnt%2 == 0:
  print(answer+min(r_cnt//2, K)*2)
elif r_cnt//2 >= K:
  print(answer+K*2)
else:
  print(answer+(r_cnt//2+1)*2-1)

Submission status: Accepted

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

rl=s.count('RL')
if s[0]=='L':
    start=1
else:
    start=0
if s[-1]=='R':
    end=1
else:
    end=0
a=rl-k
if a>=1:
    ans=a*2+start+end
elif a==0:
    ans=start+end
elif a<=-1:
    ans=1
print(n-ans)

Submission status: Accepted

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

Submission status: Accepted

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

for i,j in groupby(S):
  A+=[len(list(j))-1]

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

Submission status: Accepted

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

x=0
y=0
ans=n

# if s[0]=="L":
#     y+=1
# if s[-1]=="R":
#     y+=1
# ans+=y
# s="R"+s+"L"
for i in range(n-1):
    if s[i:i+2]=="RL":
        x+=1
        # x+=1
        # ans-=2
    if s[i:i+2]=="LR":
        y+=1

x=max(x-k,0)
y=max(y-k,0)
ans=ans-x-y-1
# ans+=min(k,x-1)*2
#
# if (k-x+1>0)&(y==0):
#     ans+=1

print(ans)

Submission status: Accepted

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

S=input()
face2face=0
back2back=0
for i in range(N-1):
  if S[i]=='L' and S[i+1]=='R':
    back2back+=1
  if S[i]=='R' and S[i+1]=='L':
    face2face+=1


for i in range(K):
  face2face-=1
  back2back-=1
face2face=max(face2face,0)
back2back=max(back2back,0)
  
print(N-face2face-back2back-1)

Submission status: Accepted

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

def runLengthEncoding(s:str) -> list:
    """
    ランレングス圧縮します。リスト内に(文字,個数)の形でカウントを収納して
    Returnします。見ての通りO(N)です。
    """
    l = []
    N = len(s)
    count = 1
    char = s[0]
    for i in range(1, N):
        if char != s[i]:
            tmp = (char, count)
            l.append(tmp)

            char = s[i]
            count = 1

        elif char == s[i]:
            count += 1

    l.append((char, count))

    return l


lre = runLengthEncoding(S)

if len(lre) == 2:
    print(N-1)
    exit()

else:
    n = len(lre) // 2
    ans = None
    if K >= n:
        ans = N-1
    else:
        groups = len(lre) - 2*K

        ans = (N-1) - groups + 1

    print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
if N == 1:
    print(0)
    exit()

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

ans += min(K,cnt//2) * 2

if K > cnt//2 and S[0] != S[-1]:
    ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  s=input()
  
  # first score
  ans=0
  x=s[0]
  for i in range(1,n):
    if x==s[i]:
      ans+=1
    else:
      x=s[i] 
  print(min(ans+2*k,n-1))

  
if __name__=='__main__':
  main()

Submission status: Accepted

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

now=S[0]
a=-1
for s in S:
    a+=now==s
    now=s
a+=K*2
ans=min(N-1,a)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
  n,k=map(int,input().split())
  s=input()
  # maked group
  t=[]
  t.append(s[0])
  x=s[0]
  for i in range(1,n):
    if x!=s[i]:
      t.append(s[i])
      x=s[i]
  #print(t)
  
  j=0
  t=deque(t)
  while j<k:
    if len(t)<=2:
      print(n-1)
      exit(0)
    t.popleft()
    t.popleft()
    j+=1
    
  print(n-1-(len(t)-1))

  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def run():
    N, K = map(int, sysread().split())
    S = input()
    c = S[0]
    checkpoints = 0
    endpoints = 0
    for s in S:
        if c == 'L':
            if s == 'R':
                c = 'R'
                endpoints += 1
            else:
                continue
        elif c == 'R':
            if s == 'L':
                checkpoints += 1
                c = 'L'
            else:
                continue
    #print(checkpoints, endpoints)
    ans = N - 2 * checkpoints
    halfpoint = 0
    edge = 0
    if S[0] == 'R':
        edge += 1
    else:
        halfpoint += 1

    if S[-1] == 'L':
        edge += 1
    else:
        halfpoint += 1

    ans -= halfpoint
    val = min([checkpoints, endpoints, K])
    checkpoints -= val
    endpoints -= val
    K -= val
    ans += 2 * val

    if K > 0:
        if checkpoints > 0:
            if edge > 0:
                val = min([edge, checkpoints, K])
                K -= val
                edge -= K
                checkpoints -= K
                ans += val
    if K > 0:
        if halfpoint > 0 and endpoints > 0:
            val = min([K, halfpoint, endpoints])
            K -= val
            halfpoint -= val
            endpoints -= val
            ans += val

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

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

s_list=[]
for i in s:
    if i=="L":s_list.append(0)
    else:s_list.append(1)
start_num=s_list[0]
i=0
while k>0:
    if i>=n:break
    if s_list[i]!=start_num:
        k-=1
        while i<n and s_list[i]!=start_num:
            s_list[i]=start_num
            i+=1
    i+=1
ans=0
for i in range(n):
    if i+1<n and s_list[i]==1 and s_list[i+1]==1:
        ans+=1
    if i-1>=0 and s_list[i]==0 and s_list[i-1]==0:
        ans+=1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

cnt = 0
init_s = S[0]
pre = '_'
for i, s in enumerate(S):
    if s != init_s:
        if pre != s:
            K -= 1
        if K == -1:
            break
        S[i] = init_s
    pre = s
ans = 0
pre = '_'
for s in S:
    ans += pre == s
    pre = s
print(ans)

Submission status: Accepted

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

L_record = []
R_record = []

if s[0] == "L":
    flg = "R"
else:
    flg = "L"

for i, char in enumerate(s):
    if char == "L" and flg == "R":
        L_record.append([i, 1])
        flg = "L"
    elif char == "L" and flg == "L":
        L_record[-1][1] += 1
    elif char == "R" and flg == "L":
        R_record.append([i, 1])
        flg = "R"
    elif char == "R" and flg == "R":
        R_record[-1][1] += 1

L_record.sort(key=lambda x: x[0])
R_record.sort(key=lambda x: x[0])
#print(L_record, R_record)

if L_record != []:
    if L_record[-1][0] + L_record[-1][1] == n:
        record = L_record.pop()
        L_record = [record] + L_record
if R_record != []:
    if R_record[-1][0] + R_record[-1][1] == n:
        record = R_record.pop()
        R_record = [record] + R_record


point = 0
for i, char in enumerate(s):
    #print(i, char)
    if char == "L" and i-1 >= 0:
        if s[i-1] == "L":
            point += 1
            #print(point)
    if char == "R" and i+1 < n:
        if s[i+1] == "R":
            point += 1
            #print(point)
#print(point)

#L -> R
point_l = point
for i in range(k):
    if L_record != []:
        idx, num = L_record.pop()
        if idx == 0:
            point_l += 1
        elif idx + num == n:
            point_l += 1
        else:
            point_l += 2

point_r = point
for i in range(k):
    if R_record != []:
        idx, num = R_record.pop()
        if idx == 0:
            point_r += 1
        elif idx + num == n:
            point_r += 1
        else:
            point_r += 2
print(min(max(point_r, point_l), n-1))

Submission status: Accepted

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

import copy

# left to right, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i, j in enumerate(s):
    if j == 'L':
        tmp_s[i] = 'R'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'R'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = cnt
# right to left, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i in range(n-1, -1, -1):
    j = s[i]
    if j == 'L':
        tmp_s[i] = 'R'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'R'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

# left to right, change R into L
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i, j in enumerate(s):
    if j == 'R':
        tmp_s[i] = 'L'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'L'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

# right to left, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i in range(n-1, -1, -1):
    j = s[i]
    if j == 'R':
        tmp_s[i] = 'L'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'L'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

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

if c <= 2 * K:
    print(N - 1)
else:
    a = c - 2 * K
    print(N - a - 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
print(min(n-1,c+2*k))

Submission status: Accepted

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

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

Submission status: Accepted

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

first = s[0]
second = 'R' if first=='L' else 'L'

i = 0
while k > 0 and i < n:
    if s[i] ==second:
        while i < n and  s[i] == second:
            s[i] = first
            i += 1
        k -= 1
    else:
        i += 1

# print(s)

ans = 0

def happy_check(i):
    global ans
    if i < n-1 and s[i] == 'R' and s[i+1] == 'R':
        ans += 1
    elif 0 < i and s[i] == 'L' and s[i-1] == 'L':
        ans += 1

for i in range(n):
    happy_check(i)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()

cnt = 0
for i in range(N - 1):
    cnt += 1
    if S[i] != S[i + 1]:
        q.append(cnt)
        cnt = 0

q.append(cnt + 1)

for _ in range(K):
    if not q:
        break
    a = q.popleft()
    b = q.popleft() if q else 0
    c = q.popleft() if q else 0
    q.appendleft(a+b+c)

print(sum(q) - len(q))

Submission status: Accepted

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

ans  = 0
tran = 0

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

    if chk == 'LR' or chk == 'RL':
        tran += 1
    else:
        ans += 1

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()