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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
S = S()

count = 0
nokori = 0
prev = None
for s in S:
  if prev != s:
    nokori += 1
  else:
    count += 1
  prev = s
  
print(count+min(nokori-1,K*2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import groupby

# RUN LENGTH ENCODING
def runLengthEncode(S: str):
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, str(len(list(v)))))
    return res

def runLengthdecode(L: "list[tuple]"):
    res = ""
    for c, n in L:
        res += c * int(n)
    return res

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    S = input()
    compressed = runLengthEncode(S)

    # ある区間を反転させるとその両端が前後で連結するようにするのが最大化できる = 両端の操作は損
    for k in range(K):
        i = 2 * k + 1   # 奇数インデックスのみ反転させる。
        if i >= len(compressed):
            break
        compressed[i] = ('L', compressed[i][1]) if compressed[i][0] == "R" else ('R', compressed[i][1])

    reCompressed = runLengthEncode(runLengthdecode(compressed))
    ans = N - len(reCompressed)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    かわいそうな人たち = s.count('LR') + s.count('RL')
    t = min(かわいそうな人たち, k)
    u = n - (かわいそうな人たち + 1) + 2 * t
    print(min(n - 1, u))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
from itertools import groupby as gb
var=[len(list(b)) for a,b in gb(s)]
ans=n-len(var)
G=len(var)
if s[0]==s[-1]:
    t=G//2
    h=G-G//2+2
else:
    t,h=G-G//2,G//2+2
#print(f"{t=},{h=},{k=},{ans=},")
if k>min(t,h):
    print(n-1)
elif k==min(t,h):
    print(n-1)
else:
    print(ans+2*k)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L=list(input())
cnt=0
if L[0]=='R' and L[1]=='R':
	cnt+=1 

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

if L[n-1]=='L' and L[n-2]=='L':
	cnt+=1

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

Submission status: Accepted

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

Submission status: Accepted

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

B = input()
happy = 0
for i in range(n):
  if B[i]=="L" and i != 0 :
    if B[i-1] == "L":
      happy +=1
  if B[i]=="R" and i != n-1 :
    if B[i+1] == "R":
      happy +=1
print(min(happy+2*k, n-1))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()
c=0
d=0
for i in range(n-1):
    if S[i]==S[i+1]:
        c+=1
    if S[i]!=S[i+1]:
        d+=1
d=(d+1)//2
print(c+2*d-1 if (d<=k and S[0]!=S[-1]) else c+2*min(d,k))

Submission status: Accepted

Solution code:
N, K = [int(_c) for _c in input().split(" ")]
S_orig = input()
point_list = []
for target, non_target in zip(["L", "R"], ["R", "L"]):
    S = list(S_orig)

    start_idx_list = []
    before_char = None
    for i, c in enumerate(S):
        if i == 0:
            start_idx_list.append(i)
            before_char = c
        else:
            if before_char == non_target and c == target:
                start_idx_list.append(i)
            before_char = c
    start_idx_list.append(len(start_idx_list) - 1)
    if len(start_idx_list) - 1 <= K:
        point_list.append(len(S) - 1)
        continue

    longest = 0
    start_idx = -1
    end_idx = -1
    for i in range(len(start_idx_list) - K):
        cur_length = start_idx_list[i + K] - start_idx_list[i] + 1
        if cur_length > longest:
            start_idx = start_idx_list[i]
            end_idx = start_idx_list[i + K]
            longest = cur_length

    for _idx in range(start_idx, end_idx):
        S[_idx] = target
    S = ["N"] + S + ["N"]

    point = 0
    for idx in range(1, N + 1):
        if S[idx] == "L":
            if S[idx + 1] == "L":
                point += 1
        if S[idx] == "R":
            if S[idx - 1] == "R":
                point += 1

    point_list.append(point)

print(max(point_list))

Submission status: Accepted

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

cnt = 0
for s, s_ in zip(S, S[1:]):
    if s == s_:
        cnt += 1

unhappy = N - 1 - cnt

print(cnt + min(unhappy, 2 * K))

Submission status: Accepted

Solution code:

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

temp = S[0]
cnt = 1
c_cnt = 1
ans = 0

for i in range(1, N+1):
  if temp == S[i]:
    cnt += 1
  else:
    ans += cnt - 1
    cnt = 1
    c_cnt += 1
    temp = S[i]
  #print(ans, cnt, c_cnt, temp)

#最後の余計な分
c_cnt -= 1

if c_cnt//2 <= K:
  if c_cnt%2 == 0:
    ans += (c_cnt//2) * 2 - 1
  else:
    ans += (c_cnt//2) * 2
else:
  ans += K * 2

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(input())
i=1
count =0
owari = False
while i < N:
    if S[i]!=S[0]:
        for j in range(i,N,1):
            if S[j]!=S[0]:
                S[j]=S[0]
            else:
                i = j
                break
            if j==N-1:
                i=N
        count+=1
        if count >= K:
            owari = True
    i+=1
    if owari:
        break
score=0
for i in range(0,N,1):
    if S[i]=="R":
        if i < N-1 and S[i+1]==S[i]:
            score+=1
    else:
        if i > 0 and S[i-1]==S[i]:
            score+=1
print(score)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def calc_happiness(S):
    cnt = 0
    for i in range(1, len(S)):
        if S[i-1] == S[i]:
            cnt += 1
    return cnt

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

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    N, K = map(int, input().split())
    S = list(input())
    gr = groupby(S)
    cnt = 0
    happy = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            happy += 1
    for key, group in gr:  # groupはイテレータ。list(group)でリスト化
        """ex.
        0: [0, 0, 0]
        1: [1, 1]
        0: [0, 0, 0]
        1: [1, 1]
        0: [0]
        1: [1]
        """
        cnt += 1
    cut = cnt-1
    while K > 0:
        if cut == 0:
            break
        elif cut >= 2:
            happy += 2
            cut -= 2
        else:
            happy += 1
            cut -= 1
        K -= 1

    print(happy)

resolve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s = list(input())
cnt=0
now=s[0]
for i in range(1,n):
    if now==s[i]:continue
    else:
        cnt+=1
        now=s[i]

ans=n-1-cnt
#syo=cnt//2
#print(ans)
print(min(n-1,ans+2*k))

Submission status: Accepted

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

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

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

if K <= m:
    happy += 2*K
else:
    if m > 1:
        happy += 2*m
    if S[0] != S[N-1]:
        happy += 1
print(happy)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    s = list(input())

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

    kaisu = (cnt + 1) // 2
    tmp = -1 if cnt % 2 else 0

    ans = min(2 * kaisu + tmp, 2 * k)

    print(ans + happy)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def calc_happiness(S):
    cnt = 0
    for i in range(1, len(S)):
        if S[i-1] == S[i]:
            cnt += 1
    return cnt

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

Submission status: Accepted

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

cnt = 0
for i in range(len(s)):
	if s[i] == 'L':
		if i == 0:
			continue
		if s[i-1] == 'L' :
			cnt += 1
	else:
		if i == len(s) - 1:
			continue
		if s[i+1] == 'R' :
			cnt += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
x, y = 0, 0
if S[0] == "L":
    y += 1
if S[-1] == "R":
    y += 1
x = S.count("RL")
if x:
    if x > K:
        x -= K
        K = 0
    else:
        K -= x
        x = 0
if K > 0:
    y = max(1, y - K)
print(N - 2 * x - y)

Submission status: Accepted

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

start = s[0]
end = s[-1]

count = 0
flag = 0
answer = 0
for i in range(1,n):
    if s[i-1] == start and s[i] != start and flag == 0:
        flag += 1
    elif s[i-1] != start and s[i] == start and flag == 1:
        flag = 0
        count += 1
    if s[i-1] == s[i]:
        answer += 1
#%%
answer += min(count,k)*2
if k > count:
    answer += flag

print(answer)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

# LRLRRL
#    ↑
# 反転させると
# LLLRLL
#  ↑↑  ↑
# また反転させると
# LLLLLL
#  ↑↑↑↑↑

# 反転させると最大2人まで幸福な人を増やせる
N, K = getNM()
s = input()
cnt = 0
for i in range(N - 1):
    if s[i] == s[i + 1]:
        cnt += 1
print(min(cnt + 2 * K, N - 1))

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input()
s += '#'
lis = []
cnt = 0
for i in range(n):
    cnt += 1
    if s[i] != s[i+1]:
        lis.append(cnt)
        cnt = 0
#print(lis)
val = 0
ans = 0
for i in range(len(lis)):
    if i < 2*k+1:
        val += lis[i]
    else:
        ans += lis[i] - 1
ans += val - 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

num = Ss.count('LR') + Ss.count('RL')
num -= 2*K
if num < 0:
    num = 0

ans = N - (num+1)
print(ans)

Submission status: Accepted

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

l = []
t = []
st = s[0]
for c in s[1:]:
    if not st or st[-1] == c:
        st += c
    else:
        l.append(len(st))
        t.append(st)
        st = c
l.append(len(st))
t.append(st)

print(len(''.join(t[:k*2])) + sum(map(lambda x: x-1, l[k*2:] if l[k*2:] else [0])))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
s = read().rstrip().decode()
ans = n - 1
for bf, af in zip(s, s[1:]):
    if bf != af:
        ans -= 1
print(min(n - 1, ans + k * 2))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    s=input()
    cunt=0
    for i in range(n-1):
        if s[i]!=s[i+1]:
            cunt+=1
    print(n-1-cunt+min(2*k,cunt))

if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D - Face Produces Unhappiness

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

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

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
#LとRが入れ替わる回数-2Kが、終わった後の入れ替わる数
#Total-入れ替わる数-1がこたえ

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

Submission status: Accepted

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

ans = 0

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

cnt = s.count('RL')
ans = 0

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


if cnt >= k:
    ans += 2*k
else:
    ans += 2*cnt
    if k-cnt>=2:
        if s[-1] == 'L' and s[0] == 'L':
            ans += 2
        elif s[-1] == 'L' or s[0] == 'L':
            ans += 1
    else:
        if s[-1] == 'L' or s[0] == 'L':
            ans += 1       


print(min(ans,n-1))

Submission status: Accepted

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

Submission status: Accepted

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

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

print(min(count+2*K, len(S)-1))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
v = s[0]
cnt = 0
a = []
for t in s:
    if t == v:
        cnt += 1
    else:
        a.append(cnt)
        cnt = 1
        v = t
a.append(cnt)
la = len(a)
b, c = [0] * (la + 1), [0] * (la + 1)
for i in range(1, la + 1):
    b[i] = b[i - 1] + a[i - 1]
    c[i] = b[i] - i
l = 2 * k + 1
if la < l:
    print(n - 1)
    exit()
ans = 0
i, j = l, 0
while True:
    ans = max(ans, b[i] - b[j] + c[la] + c[j] - c[i] - 1)
    i += 1
    j += 1
    if i > la:
        print(ans)
        exit()

Submission status: Accepted

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

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ika tako

n, k = list(map(int, input().split()))
s = input()
group = 1
for c, d in zip(s, s[1:]):
    if c != d:
        group += 1
print(n - max(1, group - 2 * k))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, k = Is()
s = S()

contl = 0
contr = 0
sandl = 0
sandr = 0


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

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

Submission status: Accepted

Solution code:
inf = 10**15
mod = 10**9+7
n, k = map(int, input().split())
s = input()
count = 0
flag = False
for c in s:
    if c == 'R':
        if flag == False:
            flag=True
    else:
        if flag == True:
            count+=1
            flag=False
if s[-1]=='R' and count > 0:
    count+=1

if k >= count:
    print(n-1)
elif k == count-1:
    if s[0] == 'R' and s[-1] == 'R':
        print(n-1)
    elif s[0] == 'R' or s[-1] == 'R':
        print(n-2)
    else:
        print(n-3)
else:
    if s[0] == 'R' and s[-1] == 'R':
        print(n - 3 - (count - 2 - k) * 2)
    elif s[0] == 'R' or s[-1] == 'R':
        print(n - 2 - (count - 1 - k) * 2)
    else:
        print(n - 1 - (count - k) * 2)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
d = 0
for c1, c2 in zip(s, s[1:]):
    if c1 == 'R' and c2 == 'L':
        d += 1
e = 0
if s[0] == 'L':
    e += 1
if s[-1] == 'R':
    e += 1
k, d = max(k - d, 0), max(0, d - k)
if k > 0:
    e = 1
ans = max(0, n - d * 2 - e)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

target = "R" if s[0] == "L" else "L"
s = "N" + s + "N"
happy_count = 0
position = []
for i in range(1, len(s)-1):
    if s[i] == "R" and s[i+1] == "R":
        happy_count += 1
    elif s[i] == "L" and s[i-1] == "L":
        happy_count += 1
    if s[i] == target and s[i+1] != target:
        position.append(i)

for i in range(len(position)):
    if k == 0:
        break
    if position[i] == n:
        happy_count += 1
    else:
        happy_count += 2
    k -= 1

print(happy_count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
point = 0
tmp = 'N'
for i in s:
    if i == tmp: point += 1
    tmp = i
rl = s.count('RL')
lr = s.count('LR')
print(point + min(2 * k, rl + lr))

Submission status: Accepted

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

def solve(S):
    ans = 0
    switch = 0
    for i in range(1,N):
        if S[i]!=S[i-1]:
            switch += 1
    switch = max(0,switch-K*2)
    ans = N-switch-1
    return ans
print(solve(S))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	S = inputStr()
	S_tmp = []

	ans = 0
	tmp = ""
	for i,val in enumerate(S):
		if i == 0:
			tmp = val
			S_tmp.append(val)
			continue

		if tmp == val:
			ans += 1
		else:
			S_tmp.append(val)
			tmp = val

	#print(S_tmp)
	#print(ans)

	kugiri = len(S_tmp)
	for i,val in enumerate(S_tmp):
		if K == 0:
			break
		K -= 1
		if kugiri <= 1:
			break
		elif kugiri == 2:
			kugiri -= 2
			ans += 1
		else:
			kugiri -= 2
			ans += 2

	#print(S_tmp)
	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()