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 = input()

left_ac = [0]
right_ac = [0]

prev = ""
for i in range(N):
    s = S[i]
    if s == "L":
        if i - 1 >= 0:
            if S[i - 1] == "L":
                left_ac.append(left_ac[-1] + 1)
            else:
                left_ac.append(left_ac[-1])
        else:
            left_ac.append(left_ac[-1])
        right_ac.append(right_ac[-1])
    else:
        if i + 1 < N:
            if S[i + 1] == "R":
                right_ac.append(right_ac[-1] + 1)
            else:
                right_ac.append(right_ac[-1])
        else:
            right_ac.append(right_ac[-1])
        left_ac.append(left_ac[-1])
left_ac.pop(0)
right_ac.pop(0)
print(min(N-1, right_ac[-1] + left_ac[-1] + 2 * K))

Submission status: Accepted

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

ranlength_l = []
count = 1
if(N==1):
    ranlength_l.append([S[0],1])
else:
    for i in range(1,len(S)):
        if(S[i] != S[i-1]):
            ranlength_l.append([S[i-1],count])
            count = 1
        else:
            count += 1
        if(i==len(S)-1):
            ranlength_l.append([S[len(S)-1],count])

ans = N-len(ranlength_l)
for const in (ranlength_l[1:-1:2]):
    if(K==0):
        break
    ans += 2
    K = K-1

if(K!=0 and len(ranlength_l)!=1):
    ans+=1

print(min([ans,N-1]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(input())
temp = S[0]
ind = 0
cs = [1]
for i in range(N - 1):
  if S[i] == S[i + 1]:
    cs[ind] += 1
  else:
    cs.append(1)
    ind += 1
    temp = S[i + 1]
#print(cs)
cscs = [cs[0]] + [0] * (len(cs))
for i in range(len(cs) - 1):
  cscs[i + 1] = cscs[i] + cs[i + 1]
cscs = [0] + cscs
css = [cs[0]] + [0] * (len(cs))
for i in range(len(cs) - 1):
  css[i + 1] = css[i] + cs[i + 1] - 1
css = [0] + css
#print(css)
#print(cscs)
res = 0
for i in range(len(css) - 2 * M):
  temp = css[-2] - css[i + 2 * M] + css[max(i, 0)]
  #print(temp,css[-2],css[i + 2 * M],css[max(i - 1, 0)])
  res = max(res, cscs[i + 2 * M] - cscs[i] + temp)
  #print(res - 1, i, i + 2 * M)
if len(css) - 2 <= 2 * M + 1:
  print(N - 1)
else:
  print(res - 1)

Submission status: Accepted

Solution code:
import math
n,k = map(int, input().split())
lst = list(input())
hap = 0
for i in range(n-1):
    if lst[i]==lst[i+1]:
        hap+=1
unh = len(lst)-hap-1
print(len(lst)-1 if math.ceil(unh/2)<=k else hap+k*2)

Submission status: Accepted

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

if n == 1:
        print(0)
else:        
        t = []
        tt = 0
        ss = s[0]
        for i in range(1,n):
                if s[i] != ss:
                        t.append(i - tt)
                        tt = i
                        ss = s[i]
        t.append(n - tt)
        cnt = sum(t) - len(t) 

        if len(t) % 2 == 0:
                if k <= (len(t) - 2)/2:
                        cnt += 2 * k
                else:
                        cnt += 2 * (len(t) - 2)/2 + 1
        else:
                if k <= (len(t) - 1)/2:
                        cnt += 2 * k
                else:
                        cnt += 2 * (len(t) - 1)/2
        print(int(cnt))

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:
N, K = map(int, input().split())
S = list(input())

c = 0
p = 0
for i, s in enumerate(S):
    if i == 0:
        pres = s
        continue
    elif s != pres:
        c += 1
    else:
        p += 1
    pres = s

if c == 0 or c == 1 or c <= 2*K:
    ans = N-1
else:
    ans = p+2*K
print(ans)

Submission status: Accepted

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

print(min(n - 1, n - (gn - k*2)))

Submission status: Accepted

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

Submission status: Accepted

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

num = s.count('LR') + s.count('RL') + 1

ans = n - max(1, num-2*k)
print(ans)

Submission status: Accepted

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

init = 0

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

print(min(init + NK[1]*2, NK[0]-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 = list(input())
a = S[0]
cur = 0
cnt = 0
for i in range(N):
    if S[i] != a:
        cnt += i-cur-1
        a = S[i]
        cur = i
if S[N-1]==a:
    cnt += N-cur-1
print(min(cnt+2*K,N-1))

Submission status: Accepted

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

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

Submission status: Accepted

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

sut = 0
a = ""
for i,s in enumerate(b):
    if i < n-1:
        if b[i] == b[i+1]:
            sut += 1
        else:
            a += s
    else:
        a+=s
a

count = len(a)
for i in range(k):
    if count <= 1:
        break
    elif count >= 3:
        sut += 2
        count -= 2
    elif count == 2:
        sut += 1
        break
print(sut)

Submission status: Accepted

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

Submission status: Accepted

Solution code:


N, K = [int(s) for s in raw_input().split(" ")]
S = raw_input()

res, same, diff = 0, 0, 0
for i in xrange(len(S)-1):
    if S[i+1] == S[i]:
        same += 1
    else:
        diff += 1

res = same + min(diff, K* 2)
print(res)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
sum = 0
dis = 0
for i in range(N-1):
    if S[i]== S[i+1]:
        sum+=1
    else:
        dis+=1
l = (dis+1)//2
if (S[0]!=S[-1]) and (l<=K):
    sum-=1
print(sum+2*min(K,l))

Submission status: Accepted

Solution code:
import sys

def solve():
    N, K = map(int, input().split())
    S = input()
    point = 0
    if S[0] == "R" and S[1] == "R": point += 1
    for i in range(1, N - 1):
        if S[i] == "L":
            if S[i-1] == "L": point += 1
        else:
            if S[i+1] == "R": point += 1
    if S[N-1] == "L" and S[N-2] == "L": point += 1

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

cnt.append(tmp)
bn = 1 + 2 * K
if len(cnt) <= bn:
    print(N - 1)
    exit(0)
ans = sum(cnt) - (len(cnt) - bn + 1)
print(ans)

Submission status: Accepted

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

def count_diff(a,b):
    cnt = 0
    for c1,c2 in zip(a, b):
        if c1 != c2:
            cnt += 1
    return cnt

s2 = s[1:]
cnt = count_diff(s[:-1], s2)
init = n - cnt - 1

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import*
n,k=map(int,input().split())
l=sorted([len(list(g)) for k,g in groupby(input())])[::-1]
t=min(2*k,len(l))
a=sum(l[:t])+sum(x-1 for x in l[t:])
print(a-(a==n))

Submission status: Accepted

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

cnt = 0
for i in range(0,len(S)):
    if i == len(S) - 1 and S[i] == "R":
        cnt = cnt
    elif i > 0 and  S[i-1] == "L" and S[i] == "L":
        cnt += 1
    elif S[i] == "R" and S[i+1] == "R":
        cnt += 1
    i += 1
print(min(cnt + 2 * K, N - 1))

Submission status: Accepted

Solution code:
from itertools import groupby
n,k=map(int,input().split())
l=sorted([len(list(g)) for k,g in groupby(input())])[::-1]
ans=sum(l[:min(2*k,len(l))])+sum(x-1 for x in l[min(2*k,len(l)):])
print(ans-(ans==n))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
S = input()

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

cur = S[0]
A = []
st = 0
tmp = is_ok[0]
for i in range(1, N):
    if S[i] == cur:
        tmp += is_ok[i]
    else:
        A.append((tmp, st, i, cur))
        st = i
        tmp = is_ok[i]
        cur = S[i]
A.append((tmp, st, N, cur))

LR = {'L': [], 'R': []}
for cnt, st, end, d in A:
    if st == 0 and end == N:
        pass
    elif st == 0 or end == N:
        LR[d].append(1)
    else:
        LR[d].append(2)

LR['L'].sort(reverse=True)
LR['R'].sort(reverse=True)
ans = sum(is_ok)

# if ans == N-1:
#     print(ans)
#     exit()

ans += max(sum(LR['L'][:K]), sum(LR['R'][:K]))
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate

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

L = [len(tuple(v)) for k, v in groupby(S)]

A = [0] + list(accumulate(L))
M = len(A)

if M <= 2 * K + 1:
    print(max(0, A[-1] - A[0] - 1))
    quit()

D = 2 * K + 1
ans = 0
for i in range(M - D):
    l = max(0, A[i] - A[0] - i)
    c = max(0, A[i + D] - A[i] - 1)
    r = max(0, A[-1] - A[i + D] - (M - 1 - i - D))

    ans = max(ans, l + c + r)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
cnt1 = 0
cnt2 = 0
if len(S) == 1:
    print(0)
    exit()
p = 0
if 'L' == S[0]:
    for i in range(N):
        if 'L' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break
else:
    for i in range(N):
        if 'R' == S[i]:
            p += 1
        else:
            ind = i
            if i == N-1:
                print(p-1)
                exit()
            break
if p == N:
    ind = N-1
ans = [1]
for i in range(ind, N):
    if S[i] == 'L':
        if cnt2:
            ans.append(2)
            cnt2 = 0
        cnt1 += 1
    else:
        if cnt1:
            ans.append(2)
            cnt1 = 0
        cnt2 += 1
if cnt1:
    ans.append(1)
else:
    ans.append(1)

ans.sort()
ans.reverse()

sums = 0
for i in range(N-1):
    if 'LL' == S[i:i+2]:
        sums += 1
    elif 'RR' == S[i:i+2]:
        sums += 1

if K >= len(ans):
    print(len(S) - 1)
else:
    if len(ans) == 0:
        print(len(S) - 1)
    if sums + sum(ans[:K]) >= len(S):
        print(len(S) - 1)
    else:
        print(sums + sum(ans[:K]))

Submission status: Accepted

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

res = 0
pre = None
add = {2: 0}
add[1] = 0 if S[0] == S[-1] else 1
for s in S:
    if pre is None:
        pass
    elif pre == s:
        res += 1
    elif pre == "R":
        add[2] += 1

    pre = s

if add[2] > K:
    res += 2 * K
    print(res)
else:
    res += 2 * add[2]
    K -= add[2]
    if add[1] == 1 and S[-1] == "L":
        res -= 2
    if K > 0:
        res += add[1]
    print(res)

Submission status: Accepted

Solution code:

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

    return ans


def count2(S):
    ans = 0
    for i in range(len(S) - 1):
        if S[i] != S[i + 1]:
            ans += 1

    return ans


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

first = count(S)
rest = count2(S)

ans = first + min(rest, K * 2)

print(ans)

Submission status: Accepted

Solution code:
def count_happiness(S):
    happiness = 0
    for n in range(N):
        if(S[n] == "L" and n > 0 and S[n] == S[n-1]):
            happiness += 1
        elif(S[n] == "R" and n < N -1 and S[n] == S[n+1]):
            happiness += 1
    return happiness

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

LR_RL_unhappy_pair = 0
LR_unhappy = 0
RL_unhappy = 0
for n in range(N-1):
    if(S[n] == "R" and S[n+1] == "L"):
        RL_unhappy += 1
    if(S[n] == "L" and S[n+1] == "R"):
        LR_unhappy += 1

change_pair_count  = min(K, min(RL_unhappy, LR_unhappy))
change_single_count = 0
if(K > change_pair_count):
    remain = K - change_pair_count
    changable = abs(RL_unhappy  - LR_unhappy)
    change_single_count = min(remain, changable) 
print(count_happiness(S) + 2 * change_pair_count + change_single_count)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
S = input()+'K'
S_c = []
cnt = 0
for i in range(n):
  if S[i+1]==S[i]:
    cnt += 1
  else:
    cnt += 1
    S_c.append(cnt)
    cnt = 0
    

if 2*k+1 <= len(S_c):
  ans = sum(S_c[:2*k+1])-1

  for i in range(2*k+1,len(S_c)):
    ans += S_c[i]-1
  print(ans)
else:
  print(sum(S_c)-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import math
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 一括読み
#N, K, *A = map(int, open(0).read().split())


# 整数の入力
#n = int(input())

# スペース区切り文字列の入力
#n, k = input().split()

# スペース区切りの整数の入力
n, k = map(int, input().split())
#n, x = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#a = [int(x) for x in input().split()]
#b = [int(x) for x in input().split()]
#print("a", a, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#b = []
#for x in range(m):
#  b.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#b = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def ton(n, k, x):
  s = ""
  while n > 0:
    s = str(n%k) + s
    n //= k
  return s


#print("a", a, file=sys.stderr)
#print("b", b, file=sys.stderr)

def getEnergy():
  for y in b:
    yield y

def doit():
  total = 0
  prev = " "
  for x in list(s):
    if prev == x:
      total += 1
    prev = x
  total += k*2
  if total >= n-1:
    return n-1
  return total

def yn():
  if doit():
    return "Yes"
  else:
    return "No"

#print(doit([0] * 4))
#doit()
#print(doit())
try:
  #doit()
  print(doit())
  #print(yn())
except Exception as e:
  print("e", e, file=sys.stderr)

Submission status: Accepted

Solution code:
import math

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

happiness = 0
unh = 0

for i in range(N-1):
    if S[i] == 'L' and S[i+1] == 'L':
        happiness +=1
    elif S[i] == 'R' and S[i+1] == 'R':
        happiness +=1
    else:
        unh +=1

if K < math.ceil(unh/2):
    happiness += 2*K
else:
    happiness = N-1

print(happiness)

Submission status: Accepted

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

c_lr = 0
c_rl = 0

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

ans = N - 1 - c_lr - c_rl

for i in range(0, K):
    if c_lr > 0 and c_rl > 0:
        c_rl -= 1
        c_lr -= 1
        ans += 2
    elif c_lr > 0:
        c_lr -= 1
        ans += 1
    elif c_rl > 0:
        c_rl -= 1
        ans += 1

print(ans)

Submission status: Accepted

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

d = []
p = 0
for i in range(1,n):
    if s[i] == s[i-1]:
        p += 1
        
    else:
        d.append(p)
        p = 0
d.append(p)
res = sum(d)

n = len(d)


for i in range(k):
    if n >= 3:
        res += 2
        n -= 2
    elif n == 2:
        res += 1
        n -= 1
    else:
        break
print(res)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
t=list()
ans=0
count=1
for i in range(n-1):
	if s[i]==s[i+1]:
		count+=1
	else:
		if count >= 2:
			ans += count-1
		t.append(1)
		count=1
if count >= 2:
	ans += count-1
t.append(1)
if len(t) < 2*k+1:
	ans += len(t) - 1
else:
	ans += 2*k
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
s=list(input())
lrcnt=0
rlcnt=0
lrch=0
rlch=0
ans=0

for i in range(len(s)-1):
  if s[i]=='L' and s[i+1]=='R':
    lrcnt+=2
  if s[i]=='L' and s[i+1]=='L':
    ans+=1
  if s[i]=='R' and s[i+1]=='L':
    rlcnt+=2
  if s[i]=='R' and s[i+1]=='R':
    ans+=1
if s[0]=='R':
  lrch+=1
else:
  rlch+=1
if s[-1]=='L':
  lrch+=1
else:
  rlch+=1

if min(lrcnt,rlcnt)>=k*2:
  ans+=k*2
else:
  tmp=min(lrcnt,rlcnt)
  ans+=tmp
  k-=tmp//2
  lrcnt-=tmp
  rlcnt-=tmp

  if k>=2:
    if lrcnt>0 and rlch>0:
      ans+=1
    if rlcnt>0 and lrch>0:
      ans+=1
  else:
    if lrcnt>0 and rlch>0:
      ans+=1
    else:
      if rlcnt>0 and lrch>0:
        ans+=1
  
print(ans)

Submission status: Accepted

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


cut=1
for i in range(1,N):
    if S[i]!=S[i-1]:
        cut+=1
#print(cut)
if cut>2*K:
    print(N-(cut-2*K))
else:
    print(N-1)

Submission status: Accepted

Solution code:
from itertools import groupby

n, k = map(int, input().split())
print(n - max(1, sum(1 for _ in groupby(input())) - 2 * k))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
S = input()

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

cur = S[0]
A = []
st = 0
tmp = is_ok[0]
for i in range(1, N):
    if S[i] == cur:
        tmp += is_ok[i]
    else:
        A.append((tmp, st, i, cur))
        st = i
        tmp = is_ok[i]
        cur = S[i]
A.append((tmp, st, N, cur))

LR = {'L': [], 'R': []}
for i in range(len(A)):
    cnt, st, end, d = A[i]
    if st == 0 or end == N:
        LR[d].append(1)
    else:
        LR[d].append(2)

LR['L'].sort(reverse=True)
LR['R'].sort(reverse=True)
ans = sum(is_ok)

if ans == N-1:
    print(ans)
    exit()

ans += max(sum(LR['L'][:K]), sum(LR['R'][:K]))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
t = 0 # 入れ替え回数
if N == 1:
  print(0)
else:
  for i in range(N-1):
    if S[i] != S[i+1]:
      t += 1
  h = (N-1)-t # 元々の「幸福」
  h = min(h+2*K, N-1)
  print(h)

Submission status: Accepted

Solution code:
def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  n,k = map(int,input().split())
  s = input()
  
  from itertools import groupby
  
  ans = 0
  for _,g in groupby(list(s)):
    l = len(list(g))
    if l > 1:
      ans += l-1

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

if __name__ == '__main__':
  solve()

Submission status: Accepted

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

cnt = 0

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

# print(cnt)

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

print(result)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
S = input()

result = 0
unmatch_count = 0

pre = ""

init_flag = 1
for LR in S:
    if init_flag == 1:
        pre = LR
        init_flag = 0
        continue
    if pre == LR:
        result += 1
    pre = LR

unmatch_count = n - result - 1
if k*2 < unmatch_count:
    result += k*2
else:
    result += unmatch_count
print(result)

Submission status: Accepted

Solution code:
from itertools import groupby

n, k = map(int, input().split())
print(n - max(1, sum(map(bool, groupby(input()))) - 2 * k))

Submission status: Accepted

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

for i in range(k):
        if even >= 2:
            count +=2
            even -= 2
        elif even ==1:
            count+=1
            even -=2
print(str(count))

Submission status: Accepted

Solution code:
n, k = [ int(v) for v in input().split() ]
s = input()

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

p, q = 0, 0
p_list, q_list = [], []
for i in range(n):
    if s[i] == mode:
        p += 1
        if i == n-1:
            p_list.append(p)
        if q != 0:
            q_list.append(q)
        q = 0
    else:
        q += 1
        if i == n-1:
            q_list.append(q)
        if p != 0:
            p_list.append(p)
        p = 0

ans_list = [sum(p_list[:k])+ sum(q_list[:k+1])] + p_list[k:] + q_list[k+1:]

ans = 0
for i in ans_list:
    ans += i-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# 幸福度が増すパターン
# L:R--R:L  L:L---L:L +2
# R:L--L:R  R:R---R:R +2

# :R---R:L  :L---L:L  +1
# :R---R:R
# :R---R:L  :L---L:L  +1
# L:R---R

# :L---L:R

# L:R を 1
# R:L を 2
#
# 1-2 2-1


def solve(N, K, S):
    ans = 0
    last = S[0]
    lr = 0
    rl = 0
    for s in S[1:]:
        if last != s:
            if last == 'L':
                lr += 1
            else:
                rl += 1
        else:
            ans += 1
        last = s

    n = min(lr, rl)
    if n >= K:
        ans += K*2
    else:
        ans += n*2
        if lr != rl:
            ans += 1

    return ans


if __name__ == '__main__':
    N, K = map(int, input().split())
    S = input()

    ans = solve(N, K, S)

    print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

n, k = map(int, input().split())
print(n - max(1, len(list(groupby(input()))) - 2 * k))

Submission status: Accepted

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

idx = 0
dirs = []
while idx < N:
    start = idx
    dirs.append([0, 1][S[idx] == "R"])
    while idx < N and S[idx] == S[start]:
        idx += 1
    intervals.append(idx - start)

assert(sum(intervals) == N)

def calc_ans(result_dirs):
    ans = N
    if result_dirs[0] == 0:
        ans -= 1
    for i in range(len(result_dirs)-1):
        now_dir, next_dir = result_dirs[i], result_dirs[i+1]
        if now_dir == 1 and next_dir == 0:
            ans -= 2
    if result_dirs[-1] == 1:
        ans -= 1
    return ans


rest = K
result_dirs = [dirs[0]]
for now_dir in dirs[1:]:
    if rest > 0 and now_dir == 1:
        result_dirs.append(0)
        rest -= 1
    else:
        result_dirs.append(now_dir)
if rest > 0 and dirs[0] == 1:
    result_dirs[0] = 0
left_ans = calc_ans(result_dirs)

rest = K
result_dirs = [dirs[0]]
for now_dir in dirs[1:]:
    if rest > 0 and now_dir == 0:
        result_dirs.append(1)
        rest -= 1
    else:
        result_dirs.append(now_dir)
if rest > 0 and dirs[0] == 0:
    result_dirs[0] = 1
right_ans = calc_ans(result_dirs)
print(max(left_ans, right_ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input().strip())
count = 0
for i in range(len(s)):
    if (i == 0 and s[i] == 'L') or (i == len(s) - 1 and s[i] == 'R'):
        pass
    elif (s[i] == 'R' and s[i + 1] == 'R') or (s[i] == 'L' and s[i - 1] == 'L'):
        count += 1

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

print(count)

Submission status: Accepted

Solution code:
n, k = [int(h) for h in input().split()]
s_s = list(input())

count = 0
for i in range(n):
  d = s_s[i]
  if d == 'L':
    if i > 0 and s_s[i - 1] == d:
      count += 1
  else:
    if i < n - 1 and s_s[i + 1] == d:
      count += 1

count += 2 * k

ans = min(n - 1, count)
      
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(len(lr)-1):
    if lr[i] == "R":
        if lr[i+1] == "R":
            cnt+=1

for i in range(len(lr)-1,0,-1):
#     print(i)
    if lr[i] == "L":
        if lr[i-1]=="L":
            cnt+= 1
            
cnt += 2*K
print(min(N-1,cnt))

Submission status: Accepted

Solution code:
def run_length_compress(S):
  l = []
  left = 0
  for right in range(1,len(S)):
    if right != len(S) - 1:
      if S[right] != S[right - 1]:
        l.append([S[right - 1], right - left])
        left = right
      else:
        pass
    else:
      if S[right] != S[right - 1]:
        l.append([S[right - 1], right - left])
        l.append([S[right], 1])
      else:
        l.append([S[right], right - left + 1])
  return l

def main():
  n,k = map(int,input().split())
  s = input()
  l = run_length_compress(s)
  if len(l) > 1:
    count = 0
    for i in range(1, len(l), 2):
      l[i][0] = l[i-1][0]
      count += 1
      if count >= k: break
  t = ''
  for j in range(len(l)):
    t += l[j][0]*l[j][1]
  
  res = 0
  for k in range(1,n):
    if t[k-1] == t[k]:
      res += 1
  print(res)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
initial=S[0]
S01=[]
if initial=='L':
    for s in S:
        if s=='L':
            S01.append(0)
        else:
            S01.append(1)
else:
    for s in S:
        if s=='R':
            S01.append(0)
        else:
            S01.append(1)
            
count=0
T01=[0]
flag=0
for n in range(N-1):
    left=S01[n]
    right=S01[n+1]
    if left==0 and right==1:
        flag=1
    if left==1 and right==0:
        flag=0
        count+=1
    
    if flag==0:
        T01.append(0)
    elif count<K:
        T01.append(0)
    else:
        T01.append(1)
    
            
point=0
for n in range(N-1):
    left=T01[n]
    right=T01[n+1]
    if left==right:
        point+=1

print(point)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s="#"+input()+"#"
ans=0
for i in range(1,n+1):
    if s[i]=="R" and s[i+1]=="R":
        ans+=1
    if s[i]=="L" and s[i-1]=="L":
        ans+=1
a=max(s.count("LR"),s.count("RL"))
if k>=a:
    ans=n-1
else:
    ans+=2*k
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import copy

def main():

	input = sys.stdin.readline

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

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

	cmin = min(LRcount,RLcount)
	if LRcount!=RLcount:
		ne = 1
	else:
		ne = 0

		
	if K<=cmin:
		count = count+K*2
	else:
		count = count+cmin*2
		if K>cmin:
			count = count+ne

	print(count)

if __name__ == "__main__":
    main()