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:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())
s = input()

x = []
l = 0
r = 0
for i in range(n):
    if i == 0:
        if s[i] == "L":
            l += 1
        else:
            r += 1
    elif s[i] == s[i - 1]:
        if s[i] == "L":
            l += 1
        else:
            r += 1
    else:
        if s[i] == "L":
            x.append(["R", r])
            r = 0
            l = 1
        else:
            x.append(["L", l])
            l = 0
            r = 1
if l > 0:
    x.append(["L", l])
else:
    x.append(["R", r])

# print(x)
ans = 0
for i in range(n):
    if s[i] == "L":
        if i != 0 and s[i - 1] == "L":
            ans += 1
    elif i != n - 1 and s[i + 1] == "R":
        ans += 1

m = len(x)
if m > 1:
    left = [] 
    right = [] 
    for i in range(m):
        if i == 0:
            if x[i][0] == "L":
                left.append(1)
            else:
                right.append(1)
        elif i == m - 1:
            if x[i][0] == "L":
                left.append(1)
            else:
                right.append(1)
        else:
            if x[i][0] == "L":
                left.append(2)
            else:
                right.append(2)
    left.sort(reverse=True)
    right.sort(reverse=True)
    # print("left =", left)
    # print("right =", right)
    ans += max(sum(left[:k]), sum(right[:k]))
# print("ans =", ans)
print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(k):
    if no == 1:
        no -= 1
        happy += 1
        break
    no -= 2
    happy += 2
print(min(happy, n-1))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import ceil
N, K = mapint()
S = list(str(input()))

old = S[0]
lis = []
cnt = 1
for i in range(1, N):
    s = S[i]
    if s!=old:
        lis.append(cnt)
        old = s
        cnt = 1
    else:
        cnt += 1
lis.append(cnt)
for l in range(K):
    if len(lis)>=3:
        l1 = lis.pop()
        l2 = lis.pop()
        lis[-1] += (l1+l2)
    elif len(lis)>=2:
        l1 = lis.pop()
        lis[-1] += l1
        break
    else:
        break

ans = sum([i-1 for i in lis])
print(ans)

Submission status: Accepted

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

happy=0
unhappy=0
for i in range(1,n):
  if s[i]==s[i-1]:
    happy+=1
  else:
    unhappy+=1

for i in range(k):
  if unhappy==1:
    unhappy-=1
    happy+=1
    break
  unhappy-=2
  happy+=2

print(min(happy,n-1))

Submission status: Accepted

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

N,K = map(int,readline().split())
S = readline().rstrip()

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

prev = ""
res = [0]
for i in range(1, n):
    if s[i] == s[i-1]:
        res.append(0)
    else:
        res.append(1)
# print(res)

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

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    n, k = map(int, input().split())
    S = input().strip()

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

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


def resolve2():
    n, k = map(int, input().split())
    S = input().strip()

    score = 0
    diff = 0
    for i in range(1, n):
        if S[i - 1] == S[i]:
            score += 1
        else:
            diff += 1

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


if __name__ == '__main__':
    resolve2()

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    n, k = map(int, input().split())
    S = input().strip()

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    n, k = list(map(int, input().split()))
    S = list(input())
    count = 0
    h = 0
    for i in range(n - 1):
        if S[i] != S[i + 1]:
            count += 1
    b = max(0, count + 1 - 2 * k)
    print(min(n - 1, n - b))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
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 main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())

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

    count = 0
    for i in range(len(S)):
        s = S[i]
        if s == 'L' and i > 0:
            if S[i-1] == 'L':
                count += 1
        if s == 'R' and i < len(S) - 1:
            if S[i+1] == 'R':
                count += 1

    state = None
    for i in range(len(S)):
        s = S[i]
        if state is None:
            state = s
            continue
        if len(state) == 1:
            if state != s:
                state += s
        else:
            if (state == 'RL' and s == 'R') or (state == 'LR' and s == 'L'):
                count += 2
                state = s
                K -= 1
                if K == 0:
                    break

    if K > 0 and (state == 'RL' or state == 'LR'):
        count += 1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# ランレングス圧縮
compressed = []
curr = ""
for x in arr:
    if curr != x:
        compressed.append(x)
        curr = x

# 境界の個数はランレングス圧縮後の文字数 - 1
boundary = len(compressed) - 1

# 2個ずつ圧縮可能
x = max(0, boundary - 2 * k)

print(n - 1 - x)

Submission status: Accepted

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

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

if min(cnt_1, cnt_2) < k:
    res += min(cnt_1, cnt_2) * 2
    if cnt_1 != cnt_2:
        res += 1
else:
    res += k * 2

print(res)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
S = np.array(list(input()))
S = (S == 'L') * 1
inner01 = 0
outer10 = 0
happy = 0
for i in range(N - 1):
    if S[i] == S[i + 1]:
        happy += 1
    elif S[i] - S[i + 1] == 1:
        outer10 += 1
    else:
        inner01 += 1
up = min(inner01, min(K, outer10))
happy += 2 * up
if K - up >= 1 and outer10 - up >= 1 and S[0] == 1:
    happy += 1
if K - up >= 2 and outer10 - up >= 2 and S[-1] == 0:
    happy += 1
if K - up >= 1 and inner01 - up >= 1 and S[0] == 0:
    happy += 1
if K - up >= 2 and inner01 - up >= 2 and S[-1] == 1:
    happy += 1
print(happy)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
S = readline().decode()
prev = ''
total = 0
for c in S:
    if prev == c:
        total += 1
    prev = c

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
if s.count("L") == 0 or s.count("R") == 0:
    print(n-1)
else:
    if s[0] == "L":
        target = "R"
        fir = "L"
    if s[0] == "R":
        target = "L"
        fir = "R"
    cnt = 0
    mode = False
    for i in range(n):
        if s[i] != target:
            if mode:
                cnt += 1
                mode = False
                if cnt == k:
                    break
        else: # TARGET
            mode = True
            s[i] = fir
    #print(s)
    import itertools
    res = itertools.groupby(s)
    final = 0
    #print(res)
    for a,b in res:
        final += len(list(b)) -1
    print(final)

Submission status: Accepted

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

C = []

count = 0
dotti = S[0]
ans = 0

for i in range(n):
    if dotti != S[i]:
        count += 1
        dotti = S[i]
    if S[i] == "R" and i < n-1: 
        if S[i+1] == "R":
            ans += 1
    elif S[i] == "L" and i > 0: 
        if S[i-1] == "L":
            ans += 1

while k > 0:
    if count >= 2:
        ans += 2
        count -= 2
    elif count == 1:
        ans += 1
        count -= 1
        break
    else:
        break
    k -= 1

print(ans)

Submission status: Accepted

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

hp = 0
uhp = 0

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

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

Submission status: Accepted

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

    # print(N, K, S)
    ans = 0

    # RR...
    if S[0] == 'R' and S[1] == 'R':
        ans += 1

    for i in range(1, N - 1):
        cl = S[i - 1]
        cc = S[i + 0]
        cr = S[i + 1]
        if cc == 'L' and cc == cl:
            ans += 1
        elif cc == 'R' and cc == cr:
            ans += 1

    # ...LL
    if S[N - 1] == 'L' and S[N - 2] == 'L':
        ans += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

for i in range(1,n-1):
    if s[i] == "L" and s[i-1] =="L":
        hap += 1
    elif s[i] == "R" and s[i+1] == "R":
        hap += 1

rl = 0
lr = 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

tmp = min(rl,lr,k)
hap += 2 * tmp

if s[0] != s[-1] and k - tmp >0:
    hap += 1
print(hap)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# N = int(input())
N, K = [int(i) for i in input().split()]
S = input()
count_list = []
pre_s = S[0]
count = 1
for i in range(1, N):
    if S[i] == pre_s:
        count += 1
    else:
        count_list.append([pre_s, count])
        pre_s = S[i]
        count = 1
count_list.append([pre_s, count])

first = S[0]
count = 1
for i in range(1, len(count_list)):
    if count > K:
        break
    if count_list[i][0] != first:
        count_list[i][0] = first
        count += 1

count = count_list[0][1]
next_i = None
for i in range(1, len(count_list)):
    if count_list[i-1][0] == count_list[i][0]:
        count += count_list[i][1]
    else:
        next_i = i
        break

if next_i is not None:
    next_sum = sum([c[1]-1 for c in count_list[next_i:]])
    print(count-1 + next_sum)
else:
    print(count-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, K = map(int, input().split())
    S = input()
    ans = 0# 初期幸福な人数
    for i in range(N-1):
        if S[i] == S[i+1]:
            ans += 1
    M = []# 'RL'の位置を格納
    if S[0] == 'L':
        M.append(1)
        # ans -= 1
    for i in range(1,N-1):
        if S[i:i+2] == 'RL':
            M.append(2)
            # ans -= 2
    if S[N-1] == 'R':
        M.append(1)
        # ans -= 2
    M.sort(reverse=True)
    # print(M,ans)
    print(min(N-1,ans + sum(M[:K])))
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n-1):
	if s[i] == s[i+1]:
		c += 1
	if a < k:
		if s[i] == 'R' and s[i+1] == 'L':
			c += 2
			a += 1
if a < k and a + 2 <= k:
	if s[0] == 'L':
		c += 1
	if s[-1] == 'R':
		c += 1
if a < k and a + 1 >= k:
	if s[0] == 'L' or s[-1] == 'R':
		c += 1
print(min(c,n-1))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N, K = zz()
S = S()
change_points = [0]
if (N == 1):
    print(0)
    exit()
if (S[0] == S[1] == 'R'):
    ans = 1
else:
    ans = 0
for i in range(1, N):
    if S[i] == 'L':
        if (S[i - 1] == 'L'):
            ans += 1
    else:
        if (i == N - 1):
            pass
        elif (S[i + 1] == 'R'):
            ans += 1

    if (S[i] != S[i - 1]):
        change_points.append(i)
# print(change_points)
# print(ans)
ans += (2*K)

print(min(ans, N-1))

Submission status: Accepted

Solution code:
def main():
    n,k=map(int, input().split())
    s= input()
    blocks = []
    nums = []
    tmp  = s[0]
    for i in range(1,n):
        if(s[i]==s[i-1]):
            tmp += s[i]
        else:
            blocks.append(tmp)
            nums.append(len(tmp))
            tmp = s[i]
        if(i==(n-1) and len(tmp)>0):
            blocks.append(tmp)
            nums.append(len(tmp))

    j = len(blocks)
    count = 0
    ans = 0
    for i in range(1,j,2):
        blocks[i] = (blocks[i-1][0])*len(blocks[i])
        count+=1
        if count == k:
            break
    sames = 2*(k)+1

    if(sames >= len(blocks)):
        ans = (n-1)
    else:
        for i in range(sames):
            ans += nums[i]
        ans -= 1
        for i in range(sames,len(blocks)):
            ans+=len(blocks[i])-1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    S = input()
    gr = itertools.groupby(S)
    ll = []
    for c, d in gr: ll.append([c, len(list(d))])

    output = N - len(ll)
    i = 1
    for _ in range(K):
        if i == len(ll)-1: output += 1
        elif i < len(ll): output += 2
        else: break
        i += 2

    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
def ranl(lst):
    ans = []
    cnt = 1
    ini = lst[0]
    for i in range(1, len(lst)):
        if ini == lst[i]:
            cnt += 1
        else:
            ans.append(cnt)
            cnt = 1
            ini = lst[i]
    ans.append(cnt)
    return ans
s = ranl(s)
if len(s)//2 <= k:
    print(n-1)
else:
    cnt = 0
    cnt += sum(s[0:2*k+1]) - 1
    for i in range(2*k+1, len(s)):
        cnt += s[i]-1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

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

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush

def rle(lst):
    res = []
    pre, cnt = lst[0], 1
    for i in range(1, len(lst)):
        if lst[i] == pre:
            cnt += 1
        else:
            res.append((pre, cnt))
            pre = lst[i]
            cnt = 1
    res.append((pre, cnt))
    return res

def solve():
    n, k = MI()
    S = list(input())

    R = rle(S)

    score = 0
    for r in R:
        score += r[1] - 1

    l = len(R)
    for _ in range(k):
        if l > 2:
            score += 2
            l -= 2
        elif l == 2:
            score += 1
            l -= 1
        else:
            break
    print(score)






if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()
INF = 10**9 + 1


def solve():
    N, K = map(int, input().split())
    S = np.array(list(input()), dtype='str')

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

    ri = INF
    kc = 0
    fs = S[0]
    if fs == 'R':
        nfs = 'L'
    else:
        nfs = 'R'

    for i in range(N):
        if S[i] == nfs:
            ri = min(ri, i)
        elif S[i] == fs and ri != INF:
            S[ri:i] = fs
            ri = INF
            kc += 1
            if kc == K:
                break
    else:
        if ri != INF and S[-1] == nfs:
            S[ri:N] = fs

    # print(S)

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

    print(happy)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
S = input().rstrip()

# 隣あう2人の向きが同じ をカウントする
cnt = 0
for i in range(N-1):
    if S[i]==S[i+1]:
        cnt += 1

# 1回の反転で +2 される => 最大で 2K 増える
cnt += 2*K

# ただし 最大値は 全員が同じ向きを向いた場合の N-1
print(min(N-1,cnt))

Submission status: Accepted

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

for i in range(N):
  if tmp=="":
    tmp=S[i]
    cnt=1
  else:
    if S[i]==tmp:
      cnt +=1
      
  if S[i]!=tmp:
    comp.append([tmp,cnt])
    tmp=S[i]
    cnt=1
  if i==N-1:
    comp.append([tmp,cnt])
  
ans=0  
for run in comp:
  ans += run[1]-1
ans += K*2
ans = min(ans,N-1)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
"""
1度の操作で最大+2できる
隣り合う箇所はN-1
LないしRが連続している箇所をグループとして見ると、求める数は
  N-1-隣り合うグループが異なっている場所の個数
= N-1-(グループの個数-1)
"""
import sys
sys.setrecursionlimit(10**6)
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(score+2*k, n-1)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, raw_input().split())
score,d,cd = 0,None,0
s = raw_input()
for i,l in enumerate(s):
	if d != l:
		cd +=1
		d = l
	if i and s[i-1] == s[i]:  score += 1


if cd > 2:
	t = min(k,((cd - 2)+1)/2)
	k -= t
	score += 2 * t 
	cd -= 2 * t
if cd == 2 and k:
	score +=1
	cd -= 1
print score

Submission status: Accepted

Solution code:
n,k = map(int, raw_input().split())
s = raw_input()
cd = 0
d = None
for l in s:
	if d != l:
		cd +=1
		d = l
score = 0
for u,v in zip(s,s[1:]):
	if u == v:
		score +=1

if cd > 2:
	t = min(k,((cd - 2)+1)/2)
	k -= t
	score += 2 * t 
	cd -= 2 * t
if cd == 2 and k:
	score +=1
	cd -= 1
print score

Submission status: Accepted

Solution code:
n,k = map(int, raw_input().split())
s = raw_input()
cd = 0
d = None
for l in s:
	if d != l:
		cd +=1
		d = l
score = 0
for u,v in zip(s,s[1:]):
	if u == v:
		score +=1

while(k and cd > 1):

	if cd > 2:
		score += 2 
		cd -= 2
	elif cd == 2:
		score +=1
		cd -= 1
	k -=1
print score

Submission status: Accepted

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

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

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

Submission status: Accepted

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

start = s[0]
current = 1
prev = None
utility = 0
while k != 0 and current < n:
  if s[current] != start:
    if not prev:
      prev = current
    else:
      utility += 1
  elif prev:
    if current == n:
      utility += 1
    else:
      utility += 2
    k = k-1
    prev = None
  else:
    utility += 1
  current += 1

if prev:
  if current == n and k > 0:
    utility +=  1
  if start == 'L':
    prev = 'R'
  else:
    prev = 'L'
else:
  if start == 'R':
    prev = 'R'
  else:
    prev = 'L'
while current < n:
  if s[current] == prev:
    utility += 1
  prev = s[current]
  current += 1
print(utility)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, K = rl()
S = rs()

import itertools
g = list(itertools.groupby(S))

print(N-max(len(g)-1-2*K, 0)-1)