AtCoder Beginner Contest 140 - Face Produces Unhappiness

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-----
6 1
LRLRRL

-----Sample Output-----
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.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
(n, k) = map(int, input().split())
s = input()
g = []
a = 'A'
s = s + 'B'
cnt = 1
for i in s:
	if a == i:
		cnt += 1
	else:
		a = i
		g.append(cnt)
		cnt = 1
print(n - max(1, len(g[1:]) - 2 * k))


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


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


(n, k) = [int(x) for x in input().split()]
s = input()
count = 1
for i in range(n - 1):
	if s[i] != s[i + 1]:
		count += 1
print(n - max(1, count - 2 * k))


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


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


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


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


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


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


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


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


(n, k) = map(int, input().split())
s = input()
(edge, inside, cnt, ix) = (0, 0, 0, 0)
if s[0] == 'R' or s[-1] == 'R':
	edge += 1
temp = ''
s += 'L'
for i in range(n + 1):
	if i != n:
		if temp == 'R' and s[i] == 'L':
			inside += 1
		elif temp == s[i]:
			cnt += 1
	temp = s[i]
if inside >= k:
	print(min(k * 2 + cnt, n - 1))
else:
	print(min(inside * 2 + edge + cnt, n - 1))


(n, k) = map(int, input().split())
s = input()
cnt = s.count('LR') + s.count('RL') + 1
ans = n - cnt + 2 * min(k, cnt)
print(min(n - 1, ans))


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


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


(n, k) = list(map(int, input().split()))
s = input()
x = 0
y = 0
ans = n
for i in range(n - 1):
	if s[i:i + 2] == 'RL':
		x += 1
	if s[i:i + 2] == 'LR':
		y += 1
x = max(x - k, 0)
y = max(y - k, 0)
ans = ans - x - y - 1
print(ans)


(N, K) = map(int, input().split())
S = input()
h = 0
for (c0, c1) in zip(S, S[1:]):
	if c0 == c1:
		h += 1
print(h + min(N - 1 - h, K * 2))


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


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


import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter

def input():
	return sys.stdin.readline().strip()

def mp():
	return list(map(int, input().split()))

def lmp():
	return list(map(int, input().split()))
(n, k) = mp()
s = list(input())
ans = []
c = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		c += 1
	else:
		ans.append(c)
		c = 1
ans.append(c)
if len(ans) // 2 <= k:
	print(n - 1)
else:
	print(n - len(ans) + 2 * k)


(N, K) = list(map(int, input().split()))
S = list(input())
(c, s) = (0, S[0])
for n in S[1:]:
	if s == n:
		c += 1
	s = n
print(min(N - 1, c + 2 * K))


import sys
from itertools import groupby

def input():
	return sys.stdin.readline().rstrip()

def main():
	(n, k) = map(int, input().split())
	S = list(input())
	p = len(list(groupby(S))) - 2 * k
	pp = max(p, 1)
	print(n - pp)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
S = input()
dif = 1
for i in range(0, n - 1):
	if S[i] != S[i + 1]:
		dif += 1
print(n - max(1, dif - 2 * k))


(n, k) = map(int, input().split())
s = input()
prev = ''
h = 0
for c in s:
	if c == prev:
		h += 1
	prev = c
print(min(h + 2 * k, n - 1))


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


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


(N, K) = map(int, input().split())
S = input()
cnt = sum([S[i] != S[i + 1] for i in range(N - 1)])
ans = N - 1 - cnt
ans += min(2 * K, cnt)
print(ans)


(N, K) = map(int, input().split())
S = input()
x = S.count('RL')
y = int(S[0] == 'L') + int(S[-1] == 'R')
print(min(N - 1, N - 2 * x - y + 2 * K))


(N, K) = map(int, input().split())
S = input()
h = N
last = ''
for s in S:
	if s != last:
		h -= 1
	last = s
print(min(N - 1, h + 2 * K))


(n, k) = map(int, input().split())
s = input()
pre = s[0]
ans = s[0]
first = s[0]
if s[0] == 'R':
	second = 'L'
else:
	second = 'R'
for i in s[1:]:
	if i == second and k > 0:
		ans = ans + first
		pre = i
	elif i == first and pre == second:
		k -= 1
		ans = ans + i
		pre = i
	elif k == 0:
		ans = ans + i
	elif i == first and pre == first:
		ans = ans + i
pre = '0'
cnt = 0
for i in ans:
	if i == pre:
		cnt += 1
	pre = i
print(cnt)


(N, K) = list(map(int, input().split()))
s = input()
cnt = 0
for (be, af) in zip(s[:-1], s[1:]):
	if be == af:
		cnt += 1
print(min(cnt + 2 * K, N - 1))


def solve(N, K, S):
	sachi = 0
	(L_cluster, R_cluster) = (0, 1) if S[0] == 'R' else (1, 0)
	for i in range(N):
		if S[i] == 'R' and i != N - 1 and (S[i + 1] == 'R'):
			sachi += 1
		if S[i] == 'L' and i != 0 and (S[i - 1] == 'L'):
			sachi += 1
		if i > 0 and S[i] != S[i - 1]:
			if S[i] == 'R':
				R_cluster += 1
			else:
				L_cluster += 1
	ans = 0
	reverse_cluster = min(L_cluster, R_cluster)
	if K >= reverse_cluster:
		ans = N - 1
	else:
		ans = sachi + K * 2
	print(ans)

def __starting_point():
	(N, K) = list(map(int, input().split()))
	S = input()
	solve(N, K, S)
__starting_point()


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


import copy
(n, k) = list(map(int, input().split()))
s = ['R'] + list(input()) + ['L']
cnt = 0
for i in range(1, n + 1):
	if s[i] == 'L' and s[i - 1] == 'L':
		cnt += 1
	if s[i] == 'R' and s[i + 1] == 'R':
		cnt += 1
while k > 0 and cnt < n - 1:
	if n - 1 - cnt > 1:
		cnt += 2
	elif n - 1 - cnt > 0:
		cnt += 1
	k -= 1
print(cnt)


(N, K) = map(int, input().split())
S = input()
a = 0
i = 1
while i < N:
	if S[i - 1] == S[i]:
		a += 1
	i += 1
print(min(N - 1, K * 2 + a))


(n, k) = map(int, input().split())
s = input()
cou = 0
for i in range(1, n):
	if s[i - 1] != s[i]:
		cou += 1
print(n - 1 - max(0, cou - 2 * k))


(N, K) = map(int, input().split())
S = input()
print(N - 1 - max(0, len([0 for i in range(1, N) if S[i] != S[i - 1]]) - 2 * K))


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


(n, k) = map(int, input().split())
S = input()
now = '0'
cnt = 0
for s in S:
	if s != now:
		cnt += 1
	now = s
print(min(n - cnt + 2 * k, n - 1))


(n, k) = map(int, input().split())
s = input()
rl = 0
end = 0
if s[0] == 'L':
	end += 1
if s[-1] == 'R':
	end += 1
for i in range(n - 1):
	if s[i] == 'R' and s[i + 1] == 'L':
		rl += 1
ans = n - 2 * rl - end
if end == 0:
	if k >= rl:
		ans += 2 * rl
		ans -= 1
	else:
		ans += 2 * k
elif end == 1:
	if k >= rl:
		ans += 2 * rl
	else:
		ans += 2 * k
elif end == 2:
	if k == rl:
		ans += 2 * rl
	elif k >= rl + 1:
		ans += 2 * rl
		ans += 1
	else:
		ans += 2 * k
print(ans)


(N, K) = map(int, input().split())
S = input()
A = []
pre = S[0]
cnt = 1
for i in range(1, N):
	if pre == S[i]:
		cnt += 1
	else:
		pre = S[i]
		A.append(cnt)
		cnt = 1
A.append(cnt)
if len(A) == 1:
	print(N - 1)
	return
ans = sum(A) - len(A)
(X, Y) = ([0, 0], [0, 0])
for i in range(len(A)):
	if i == 0 or i == len(A) - 1:
		Y[i % 2] += 1
	else:
		X[i % 2] += 1
wk = [0, 0]
for i in range(2):
	if K <= X[i]:
		wk[i] = K * 2
	elif K <= X[i] + Y[i]:
		wk[i] = X[i] * 2 + (K - X[i])
	else:
		wk[i] = X[i] * 2 + Y[i]
print(ans + max(wk))
return
print(ans, wk)
print(A)
print(X)
print(Y)


(N, K) = (int(i) for i in input().split())
S = input()
while 'LL' in S:
	S = S.replace('LL', 'L')
while 'RR' in S:
	S = S.replace('RR', 'R')
sad = N - len(S)
sad += K * 2
sad = min(N - 1, sad)
print(sad)


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


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(MAP())
(n, k) = MAP()
s = input()
l = s.count('L')
count = 0
for i in range(n):
	if i > 0 and s[i] == s[i - 1] == 'L':
		count += 1
	elif i < n - 1 and s[i] == s[i + 1] == 'R':
		count += 1
ans = min(count + k * 2, n - 1)
print(ans)


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


def count(s):
	c = 0
	for i in range(len(s) - 1):
		if s[i + 1] == s[i]:
			c += 1
	return c
(n, k) = list(map(int, input().split()))
s = input()
a = [str(c) for c in s]
cmax = n - 1
p = count(a)
while 1:
	if p == cmax:
		break
	elif p == cmax + 1:
		p -= 1
		break
	elif k > 0:
		p += 2
		k -= 1
	else:
		break
print(p)


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


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


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


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


(N, K) = list(map(int, input().split()))
S = input()
RL = 0
for i in range(N - 1):
	if S[i] == 'R' and S[i + 1] == 'L':
		RL += 1
egde = (S[0] == 'L') + (S[-1] == 'R')
if K >= RL:
	K -= RL
	RL = 0
	if K > 0:
		egde = max(1, egde - K)
else:
	RL -= K
print(N - 2 * RL - egde)


def readinput():
	(n, k) = list(map(int, input().split()))
	s = input()
	return (n, k, s)

def main(n, k, s):
	nl = s.count('L')
	nr = n - nl
	if nl == 0 or nr == 0:
		return n - 1
	c = ['L', 'R']
	flip = []
	happy = 0
	if s[0] == 'L':
		ci = 0
	else:
		ci = 1
	l = 0
	for i in range(n):
		if s[i] == c[ci]:
			l += 1
		else:
			happy += max(l - 1, 0)
			flip.append(ci)
			l = 1
			ci = (ci + 1) % 2
	else:
		happy += max(l - 1, 0)
	return happy + min(2 * k, len(flip))

def __starting_point():
	(n, k, s) = readinput()
	ans = main(n, k, s)
	print(ans)
__starting_point()


(n, k) = map(int, input().split())
prev = ''
cnt = 0
for c in input():
	if c != prev:
		cnt += 1
	prev = c
cnt = max(1, cnt - 2 * k)
print(n - cnt)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
(n, k) = list(map(int, input().split()))
s = input()
cnt = 0
for i in range(n):
	if s[i] == s[i + 1]:
		cnt += 1
ans = min([k * 2 + cnt, n - 1])
print(ans)


def main():
	(n, k) = map(int, input().split())
	s = input()
	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))

def __starting_point():
	main()
__starting_point()


import sys
(n, k) = list(map(int, input().split()))
s = input()
lcnt = -1
rcnt = -1
rr = [0] * n
ll = [0] * n
sim = ''
for si in s:
	if si == 'R' and sim == 'R':
		rr[rcnt] += 1
	elif si == 'R' and sim != 'R':
		rcnt += 1
		rr[rcnt] = 1
	if si == 'L' and sim == 'L':
		ll[lcnt] += 1
	elif si == 'L' and sim != 'L':
		lcnt += 1
		ll[lcnt] = 1
	sim = si
ll = [i for i in ll if i != 0]
rr = [i for i in rr if i != 0]
minlen = min(len(ll), len(rr))
if minlen <= k:
	print(n - 1)
	return
for i in range(k):
	ll[i] += rr[i]
	rr[i] = 0
for i in range(len(ll) - 1):
	if i < len(rr) and ll[i] != 0 and (rr[i] == 0):
		ll[i + 1] += ll[i]
		ll[i] = 0
icnt = 0
for i in range(len(ll)):
	icnt += max(ll[i] - 1, 0)
for i in range(len(rr)):
	icnt += max(rr[i] - 1, 0)
print(icnt)


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


from fractions import gcd
from itertools import combinations, permutations, accumulate
from collections import deque, defaultdict, Counter
import decimal
import re
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7

def readInts():
	return list(map(int, input().split()))

def I():
	return int(input())
(n, k) = readInts()
S = input()
a = 0
for i in range(1, len(S)):
	if S[i] != S[i - 1]:
		a += 1
print(n - 1 - max(a - 2 * k, 0))


(a, b) = map(int, input().split())
l = list(input())
s = 0
for (n, (x, y)) in enumerate(zip(l, l[1:])):
	if x == y:
		s += 1
print(min(a - 1, s + b * 2))


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


(n, k, s) = open(0).read().split()
(n, k) = (int(n), int(k))
d = 0
for i in range(1, n):
	if not s[i] == s[i - 1]:
		d += 1
print(n - 1 - max(d - 2 * k, 0))


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 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
print(main())


(N, K) = map(int, input().split())
Ss = input()
num = Ss.count('LR') + Ss.count('RL') + 1
ans = N - max(1, num - 2 * K)
print(ans)


(n, k) = [int(i) for i in input().split()]
s = input()
ans = 0
for (i, j) in zip(s[:-1], s[1:]):
	if i != j:
		ans += 1
print(n - 1 - max(ans - 2 * k, 0))


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, K) = list(map(int, readline().split()))
	S = readline().strip()
	ans = 0
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			ans += 1
	ans += 2 * K
	if ans > N - 1:
		ans = N - 1
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


(N, K) = [int(x) for x in input().split()]
S = input()
cnt = 0
for i in range(len(S) - 1):
	cnt += S[i] == S[i + 1]
print(min(cnt + 2 * K, N - 1))


import sys
from itertools import groupby
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, K) = list(map(int, readline().split()))
	S = readline().strip()
	ans = groups = 0
	for (k, g) in groupby(S):
		ans += len(list(g)) - 1
		groups += 1
	ans += 2 * K
	if ans > N - 1:
		ans = N - 1
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
s = input()
unhappy_0 = s.count('RL') * 2 + (s[0] == 'L') + (s[-1] == 'R')
print(n - max(unhappy_0 - k * 2, 1))


(N, K) = list(map(int, input().split(' ')))
S = input()
groups = 1
for (s0, s1) in zip(S, S[1:]):
	if s0 != s1:
		groups += 1
groups = max(1, groups - 2 * K)
print(N - groups)


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


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


(N, K) = map(int, input().split())
S = input()
c = S[0]
ans = 0
for x in S[1:]:
	if x != c:
		c = x
	else:
		ans += 1
print(min(ans + 2 * K, N - 1))


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


def main():
	(n, k) = list(map(int, input().split()))
	s = input()
	hp = [0] * n
	for i in range(n):
		if i > 0:
			if s[i] == s[i - 1] == 'L':
				hp[i] = 1
		if i < n - 1:
			if s[i] == s[i + 1] == 'R':
				hp[i] = 1
	ans = sum(hp)
	ans = min(ans + 2 * k, n - 1)
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys, math
from collections import deque
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline()[:-1]

def mi():
	return map(int, input().split())

def ii():
	return int(input())

def i2(n):
	tmp = [list(mi()) for i in range(n)]
	return [list(i) for i in zip(*tmp)]

def main():
	(N, K) = mi()
	S = input()
	m = S.count('RL') + S.count('LR')
	x = N - 1 - m
	print(min(x + 2 * K, N - 1))

def __starting_point():
	main()
__starting_point()


b = list(map(int, input().split()))
n = input()
c = 0
for i in range(b[0] - 1):
	if n[i] == n[i + 1]:
		c += 1
	else:
		c = c
print(min(b[0] - 1, c + 2 * b[1]))


(n, k) = map(int, input().split())
s = input()
islands = 1
for i in range(1, len(s)):
	if s[i] != s[i - 1]:
		islands += 1
print(n - max(1, islands - 2 * k))


(N, K) = map(int, input().split())
S = input()
u = [S[0]]
for c in S:
	c == u[-1] or u.append(c)
print(len(S) - max(len(u) - 2 * K, 1))


(n, k) = map(int, input().split())
s = input()
sep = sum((a != b for (a, b) in zip(s, s[1:])))
print(n - max(0, sep - 2 * k) - 1)


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, k) = list(map(int, input().split()))
	s = input()
	cnt = 0
	score = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			cnt += 1
		else:
			score += 1
	res = min(n - 1, score + min(k, cnt) * 2)
	print(res)

def __starting_point():
	resolve()
__starting_point()


(N, K) = map(int, input().split())
S = input()
happy_face = N - 1 - S.count('LR') - S.count('RL')
ans = min(N - 1, happy_face + 2 * K)
print(ans)


(n, k) = map(int, input().split())
s = list(input())
lr = 0
rl = 0
ans = 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
	else:
		ans += 1
if lr >= k and rl >= k:
	ans += 2 * k
elif lr == rl:
	ans += 2 * lr
else:
	num = max(lr, rl)
	ans += 2 * num - 1
print(ans)


(N, K) = map(int, input().split())
S = input()
happiness = N - 1 - S.count('LR') - S.count('RL')
print(min(N - 1, happiness + 2 * K))


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(N, K) = LI()
	S = SS()
	h = 0
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			h += 1
	cnt = 0
	for i in range(N - 1):
		if S[i] != S[i + 1]:
			cnt += 1
	if cnt >= 2 * K:
		h += 2 * K
	else:
		h = N - 1
	print(h)

def __starting_point():
	resolve()
__starting_point()


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


def main():
	(N, K) = list(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)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
S = list(input())
ans = 0
for (x, y) in zip(S, S[1:]):
	if x == y:
		ans += 1
print(min(N - 1, ans + 2 * K))


(n, k) = [int(i) for i in input().split()]
s = input()
status = s[0]
cnt = 1
sa = []
for i in range(1, n):
	if s[i] != status:
		sa.append(status * cnt)
		cnt = 0
		status = s[i]
	cnt += 1
sa.append(status * cnt)
for i in range(1, min(k * 2, len(sa)), 2):
	sa[i] = ('R' if sa[i][0] == 'L' else 'L') * len(sa[i])
sa = ''.join(sa)
ans = 0
for i in range(n):
	if sa[i] == 'L':
		if i > 0:
			if sa[i - 1] == 'L':
				ans += 1
	elif i < n - 1:
		if sa[i + 1] == 'R':
			ans += 1
print(ans)


import sys

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return list(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)

def __starting_point():
	Main()
__starting_point()


(N, K) = map(int, input().split())
S = input()
count = sum((i == 0 or S[i - 1] != S[i] for i in range(N)))
print(N - max(count - 2 * K, 1))


(N, K) = map(int, input().split())
s = input()
x = 0
for i in range(N - 1):
	if s[i] != s[i + 1]:
		x += 1
x = max([0, x - 2 * K])
print(N - 1 - x)


(n, k) = map(int, input().split())
hoge = list(input())
hap = 0
for (i, j) in zip(hoge[0:], hoge[1:]):
	if i == j:
		hap += 1
print(min(hap + 2 * k, n - 1))


from collections import deque

def main():
	(n, k) = map(int, input().split())
	s = input()
	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]
	j = 0
	t = deque(t)
	while j < k:
		if len(t) <= 2:
			print(n - 1)
			return
		t.popleft()
		t.popleft()
		j += 1
	print(n - 1 - (len(t) - 1))

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
S = input()
h = 0
for i in range(N - 1):
	if i == 0 and S[i] == 'L':
		pass
	if S[i] == S[i + 1]:
		h += 1
print(min(h + 2 * K, N - 1))


(N, K) = map(int, input().split())
S = input()
n = 0
p = '0'
for s in S:
	if s != p:
		n += 1
	p = s
print(N - max(1, n - K * 2))


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


(n, k) = map(int, input().split())
s = input()
ans = 0
for (i, j) in zip(s[:-1], s[1:]):
	if i + j == 'LL' or i + j == 'RR':
		ans += 1
print(min(n - 1, ans + 2 * k))


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


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


import sys, math, collections, itertools
input = sys.stdin.readline
(N, K) = list(map(int, input().split()))
S = input().rstrip()
ori_num = 0
turn_num = 0
for i in range(N):
	if i > 0:
		if S[i - 1] == 'L' and S[i] == 'L':
			ori_num += 1
		if S[i - 1] != S[i]:
			turn_num += 1
	if i < N - 1:
		if S[i] == 'R' and S[i + 1] == 'R':
			ori_num += 1
if turn_num >= 2 * K:
	ori_num += 2 * K
else:
	num = turn_num // 2
	num2 = turn_num % 2
	ori_num += 2 * num + num2
print(ori_num)


import sys
input = sys.stdin.readline
(N, K) = (int(x) for x in input().rstrip('\n').split())
L = list(input())
now = L[0]
same = 0
for x in L[1:]:
	if x == now:
		same += 1
	else:
		now = x
res = same + K * 2
if res > N - 1:
	res = N - 1
print(res)


(N, K) = map(int, input().split())
H = input()
a = 0
for i in range(N - 1):
	if H[i] == H[i + 1]:
		a += 1
b = min(N - 1, a + 2 * K)
print(b)


(N, K) = map(int, input().split())
S = input()
if N == 1:
	print(0)
	return
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)


(n, k) = map(int, input().split())
s = input()
a = 'A'
cnt = 0
for i in s:
	if a != i:
		a = i
		cnt += 1
print(n - max(1, cnt - 2 * k))


def main():
	from itertools import tee
	(N, K) = list(map(int, input().split()))
	S = input()
	(s1, s2) = tee(S, 2)
	next(s2)
	cnt = 0
	for (c1, c2) in zip(s1, s2):
		if c1 != c2:
			cnt += 1
	ans = N - 1 - max(cnt - K * 2, 0)
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
s = input()
happiness = 0
for (c, d) in zip(s, s[1:]):
	if c == d:
		happiness += 1
ans = min(n - 1, happiness + 2 * k)
print(ans)


(n, k) = map(int, input().split())
s = input()
c = s.count
print(n - 1 - max(c('LR') + c('RL') - k * 2, 0))


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


(N, K) = map(int, input().split())
s = str(input())
ans = N - 1 - s.count('RL') - s.count('LR')
print(min(N - 1, ans + 2 * K))


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


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


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


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


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


(n, k) = map(int, input().split())
s = input()
from_start = 0
RtoL = 0
LtoR = 0
for i in range(n - 1):
	if s[i] == s[i + 1]:
		from_start += 1
	elif s[i] == 'R' and s[i + 1] == 'L':
		RtoL += 1
	elif s[i] == 'L' and s[i + 1] == 'R':
		LtoR += 1
add = 0
while (RtoL or LtoR) and k:
	k -= 1
	if RtoL and LtoR:
		add += 2
		RtoL -= 1
		LtoR -= 1
	elif RtoL:
		add += 1
		RtoL -= 1
	elif LtoR:
		add += 1
		LtoR -= 1
print(from_start + add)


def main():
	import sys

	def input():
		return sys.stdin.readline().rstrip()
	(n, k) = map(int, input().split())
	s = input()
	n = len(s)
	ans = 0
	for i in range(n - 1):
		if s[i + 1] == s[i]:
			ans += 1
	while ans < n - 1 and k > 0:
		if n - 1 - ans > 1:
			ans += 2
		elif n - 1 - ans == 1:
			ans += 1
		k -= 1
	print(ans)

def __starting_point():
	main()
__starting_point()


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


(n, k) = map(int, input().split())
(t, *s) = input()
c = 0
for d in s:
	if d == t:
		c += 1
	t = d
print(min(c + k * 2, n - 1))


(N, K) = map(int, input().split())
S = str(input())
ans = 0
for i in range(N - 1):
	if S[i] == S[i + 1]:
		ans += 1
for i in range(K):
	if N - ans > 2:
		ans += 2
	elif N - ans == 2:
		ans += 1
		break
	else:
		break
print(ans)


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


(n, k) = map(int, input().split())
S = input()
point = n - (S.count('RL') + S.count('LR')) - 1
ans = min(n - 1, point + 2 * k)
print(ans)


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


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


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))


from itertools import *
(n, k) = map(int, input().split())
print(min(sum((len(list(l)) - 1 for (_, l) in groupby(input()))) + 2 * k, n - 1))


import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)

def solve(S, N, K, LR):
	happy = 0
	one = 0
	two = 0
	prev = None
	for i in range(N + 1):
		s = S[i]
		if prev is None:
			prev = (s, i)
			continue
		if prev[0] == s:
			continue
		happy += i - 1 - prev[1]
		if prev[0] == LR:
			if prev[1] == 0 and i - 1 == N - 1:
				pass
			elif prev[1] == 0 or i - 1 == N - 1:
				one += 1
			else:
				two += 1
		prev = (s, i)
	spans = [2] * two + [1] * one
	if spans:
		happy += sum(spans[:min(K, len(spans))])
	return happy

def main():
	input = sys.stdin.readline
	(N, K) = list(map(int, input().split()))
	S = input().strip()
	S += 'D'
	happy = max([solve(S, N, K, 'L'), solve(S, N, K, 'R')])
	print(happy)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split(' '))
S = input()
happy = sum([1 for i in range(N - 1) if S[i] == S[i + 1]])
print(min(N - 1, happy + 2 * K))


(str_len, cng_cnt) = input().split(' ')
str_input = list(input())
str_len = int(str_len)
cng_cnt = int(cng_cnt)
tmp1 = ''
cnt = 0
cnt2 = 0
for st in str_input:
	if tmp1 == st:
		cnt = cnt + 1
	else:
		cnt2 = cnt2 + 1
	tmp1 = st
if cng_cnt < cnt2 - 1:
	c_up = cng_cnt * 2
else:
	c_up = cnt2 * 2 + (cng_cnt - cnt2)
ans = cnt + c_up
if ans >= str_len:
	ans = str_len - 1
print(ans)


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


(n, k) = map(int, input().split())
s = input()
unhappy = s.count('RL') + s.count('LR')
happy = n - unhappy - 1
happy = min(n - 1, happy + 2 * k)
print(happy)


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

def run_length_encoding(text: str) -> list:
	text += '_'
	c = text[0]
	x = 1
	res = []
	for i in range(1, len(text)):
		if c == text[i]:
			x += 1
		else:
			res.append((c, x))
			c = text[i]
			x = 1
	return res
rle = run_length_encoding(S)
gr = len(rle)
hp = 0
for (c, x) in rle:
	hp += x - 1
if gr == 1:
	ans = hp
elif gr == 2:
	ans = hp + 1
elif K < gr // 2:
	ans = hp + 2 * K
else:
	ans = hp + 2 * ((gr - 1) // 2) + (gr - 1) % 2
print(ans)


import sys
r = sys.stdin.readline
(N, K) = map(int, r().split())
S = r().strip()

def HappyCnt(S):
	cnt = 0
	if len(S) == 1:
		return cnt
	for i in range(1, len(S)):
		if S[i - 1] == S[i]:
			cnt += 1
	return cnt
cnt = HappyCnt(S)
LR = list(S).count('LR')
RL = list(S).count('RL')
print(min(N - 1, cnt + 2 * K))


(n, k) = [int(i) for i in input().split()]
s = input()
a = 0
for (i, ch) in enumerate(s[1:], 1):
	if ch == s[i - 1]:
		a += 1
print(min(n - 1, a + 2 * k))


from itertools import *
(a, b) = map(int, input().split())
s = input()
n = [len(list(v)) for (k, v) in groupby(s)]
print(min(sum(n) - len(n) + min(len(n) - 1, b) * 2, a - 1))


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


(N, K) = map(int, input().split())
S = input()
flips = sum((int(x != y) for (x, y) in zip(S, S[1:])))
flips = max(0, flips - 2 * K)
print(N - 1 - flips)


(N, K) = list(map(int, input().split()))
let = input()
can = 0
for i in range(N - 1):
	if let[i] != let[i + 1]:
		can += 1
if can <= K * 2:
	print(N - 1)
else:
	can -= K * 2
	print(N - can - 1)


def solve():
	(N, K) = map(int, input().split())
	S = input()
	cnt = 1
	for i in range(N - 1):
		if S[i] != S[i + 1]:
			cnt += 1
	ans = N - max(1, cnt - K * 2)
	return ans
print(solve())


(n, k) = map(int, input().split())
s = [' '] + list(input()) + [' ']
tar = now = s[1]
cnt = 0
for i in range(1, n + 1):
	if now != s[i]:
		now = s[i]
		if now != tar:
			cnt += 1
	if cnt > k:
		break
	s[i] = tar
ans = 0
for i in range(1, n + 1):
	if s[i] == 'L' and s[i - 1] == 'L':
		ans += 1
	if s[i] == 'R' and s[i + 1] == 'R':
		ans += 1
print(ans)


(N, K) = [int(x) for x in input().split()]
S = str(input())
a = 0
for i in range(N - 1):
	if S[i] == S[i + 1]:
		a += 1
b = min(N - 1, a + 2 * K)
print(b)


from itertools import accumulate
(N, K) = list(map(int, input().split()))
S = input()
q = []
pre = S[0]
ans = cnt = 0
for s in S:
	if pre != s:
		q.append(cnt)
		cnt = 1
		pre = s
	else:
		cnt += 1
q.append(cnt)
J = 2 * K + 1
acc = list(accumulate(q))
acc += [acc[-1]]
if len(q) <= J:
	ans = acc[-1] - 1
else:
	ans = acc[J - 1] - 1 + acc[-1] - acc[J] - (len(q) - J)
	for (i, a) in enumerate(acc):
		if i + J < len(q):
			tot = acc[i + J] - acc[i] - 1
			tot += acc[i] + acc[-1] - acc[i + J + 1] - (len(q) - J)
			if tot > ans:
				ans = tot
print(ans)


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


(N, K) = list(map(int, input().split()))
S = input()
if N == 1:
	print(0)
	return
if N == 2:
	if K >= 1:
		print(1)
	else:
		print(0)
		return
ans = 0
d = 0
for (i, s) in enumerate(S[:-1]):
	if S[i] == S[i + 1]:
		ans += 1
ans += 2 * K
print(min(ans, N - 1))


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 + min(2 * K, split))


(n, k) = list(map(int, input().split()))
S = input()
ans = []
c = 1
for i in range(1, n):
	if S[i - 1] == S[i]:
		c += 1
	else:
		ans.append(c)
		c = 1
ans.append(c)
if len(ans) // 2 <= k:
	print(n - 1)
else:
	d = len(ans) - 2 * k
	print(n - d)


(n, k) = list(map(int, input().split()))
S = input()
(c, row_count) = (S[0], 1)
for s in S:
	if c != s:
		c = s
		row_count += 1
if row_count - k * 2 <= 1:
	row_count = 1
else:
	row_count -= k * 2
print(n - row_count)


(n, k) = map(int, input().split())
s = input()
c = sum([s[i:i + 2] in ('LR', 'RL') for i in range(n - 1)])
print(n - c - 1 + int(min(c / 2, k) * 2))


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