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:
from bisect import bisect

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

f = S[0]

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

while i < N-1:
  f = S[i]
  for j in range(i+1,N):
    if S[j] != f:
      break
  else:
    res += 1
  res += j-i-1
  i = j
    
print(res)

Submission status: Accepted

Solution code:
N,K = 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))

Submission status: Accepted

Solution code:
N, K = 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)

Submission status: Accepted

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

happy = 0
rl = 0
before = s[0]
if before == 'R' and s[1] == 'R':
    happy += 1
for i in range(1, n):
    if before == 'R' and s[i] == 'L':
        rl += 1
    if s[i] == 'L' and s[i-1] == 'L':
        happy += 1
    if i < n-1:
        if s[i] == 'R' and s[i+1] == 'R':
            happy += 1
    before = s[i]

if rl < k:
    print(n-1)
else:
    print(happy + k*2)

Submission status: Accepted

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

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

happy = 0
lchunk, rchunk = [], []
before = s[0]
if before == 'R' and s[1] == 'R':
    happy += 1
for i in range(1, n):
    si = s[i]

    if si != before:
        if before == 'L':
            if lchunk == [] and rchunk == []:
                lchunk.append(1)
            else:
                lchunk.append(2)
        else:
            if rchunk == [] and lchunk == []:
                rchunk.append(1)
            else:
                rchunk.append(2)
    
    if si == 'L' and s[i-1] == 'L':
        happy += 1
    if i < n-1:
        if si == 'R' and s[i+1] == 'R':
            happy += 1
    before = si
if s[-1] == 'L':
    lchunk.append(1)
else:
    rchunk.append(1)

lchunk.sort(reverse=True)
rchunk.sort(reverse=True)

if lchunk == [] or rchunk == []:
    print(happy)
else:
    print(max(happy+sum(lchunk[:k]), happy+sum(rchunk[:k])))

Submission status: Accepted

Solution code:
def readinput():
    n,k=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']

    # happyの初期値を計算
    flip=[]
    happy=0
    if s[0]=='L':
        ci=0
    else:
        ci=1
    l=0
    for i in range(n):
        #print(s[i],c[ci])
        if s[i]==c[ci]:
            l+=1
            #print(l)
        else:
            #print(l)
            happy+=max(l-1,0)
            flip.append(ci)
            l=1
            ci=(ci+1)%2
    else:
        happy+=max(l-1,0)
    #print(flip,happy)
    return happy+min(2*k,len(flip))

if __name__=='__main__':
    n,k,s=readinput()
    ans=main(n,k,s)
    print(ans)

Submission status: Accepted

Solution code:
N,K=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))

Submission status: Accepted

Solution code:
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)
  exit(0)
ans = sum(A) - len(A)
# X は真ん中。Yは端っこ。引数はIndexのMOD2。
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))
exit(0)
print(ans, wk)
print(A)
print(X)
print(Y)

Submission status: Accepted

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

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 += 2 * k
if ans >= n:
    ans = n-1
print(ans)

Submission status: Accepted

Solution code:
N, K = 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)

Submission status: Accepted

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

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

    S += 'D'  # dummy

    happy = max([solve(S, N, K, 'L'), solve(S, N, K, 'R')])
    print(happy)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = 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)

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
S = readline().decode().rstrip()
cnt = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        cnt += 1 
print(min(N-1,N-cnt+2*K))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    n, k = map(int, input().split())
    s_s = list(input())

    if len(s_s) == 1:
        print(0)
        return

    # 処理
    target = []
    actcnt = 0
    for cnt, s in enumerate(s_s[1:], start=1):
        if actcnt == k:
            break
        bef_str = s_s[cnt - 1]

        if bef_str != s:
            target.append(cnt)
        if len(target) == 2:
            for work in range(target[0], target[1]):
                s_s[work] = "L" if s_s[work] == "R" else "R"
            target = []
            actcnt += 1
        if len(target) == 1 and cnt == len(s_s) - 1:
            for work in range(target[0], len(s_s)):
                s_s[work] = "L" if s_s[work] == "R" else "R"

    # 処理後、要素を数え上げる。
    ans = 0
    for cnt, s in enumerate(s_s[1:], start=1):
        bef_str = s_s[cnt - 1]
        if bef_str == s:
            ans += 1

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """6 1
LRLRRL"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """13 3
LRRLRLRRLRLLR"""
        output = """9"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10 1
LLLLLRRRRR"""
        output = """9"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """9 2
RRRLRLRLL"""
        output = """7"""
        self.assertIO(test_input, output)

    def test_input_5(self):
        test_input = """1 2
R"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_6(self):
        test_input = """10 2
LLLLLRLRLL"""
        output = """9"""
        self.assertIO(test_input, output)

    def test_input_7(self):
        test_input = """10 2
LLLLLRLRLR"""
        output = """8"""
        self.assertIO(test_input, output)

    def test_input_8(self):
        test_input = """10 1
RLLLLRLRLR"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_9(self):
        test_input = """10 1000
LLLLLRLRLL"""
        output = """9"""
        self.assertIO(test_input, output)

    def test_input_9(self):
        test_input = """10 1000
LLLLLLLLLL"""
        output = """9"""
        self.assertIO(test_input, output)

    def test_input_10(self):
        test_input = """10 1
RLLLRLLLLR"""
        output = """7"""
        self.assertIO(test_input, output)

        test_input = """10 2
RLRLRLRLRL"""
        output = """4"""
        self.assertIO(test_input, output)

        test_input = """10 3
RLRLRLRLRL"""
        output = """6"""
        self.assertIO(test_input, output)

        test_input = """10 4
RLRLRLRLRL"""
        output = """8"""
        self.assertIO(test_input, output)

        test_input = """10 5
RLRLRLRLRL"""
        output = """9"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_input_11(self):
        test_input = """10 5
RLRLRLRLRL"""
        output = """9"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 13:00:21 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N, K = list(map(int, input().split()))
  A = input()[:-1]

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

  if A[0] == 'L':
    target = 'R'
  else:
    target = 'L'

  if A[-1] == 'L':
    A += 'R'
  else:
    A += 'L'

  lim = K
  pre = A[0]
  for i in range(1, N+1):
    # if pre == A[i]:
    #   pre = A[i]
    #   continue
    # if A[i] == target:
    #   pre = A[i]
    #   continue

    if (not(pre == A[i]) and not(A[i] == target)):
      lim -= 1
      if i == N:
        origin += 1
      else:
        origin += 2
      if lim <= 0:
        break
    pre = A[i]

  print(origin)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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


if '__main__' == __name__:
    resolve()

Submission status: Accepted

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


ans = 0
d = 0
for i,s in enumerate(S[:-1]):
  if S[i] == S[i+1]:
    ans += 1
#print(ans)
ans += 2*K
print(min(ans,N-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2020/05/16/005300

def main():
    from itertools import tee

    N, K = 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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
s=input()

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

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

print(min(happy,n-1))

Submission status: Accepted

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

#グループの個数
cnt = 1

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

print(N - max(1, cnt - 2*K))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
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))

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = 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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def getmoji(k):
    return chr(ord("a") + k)

def main():
    n, k = getList()
    s = getS()

    ko, fuko = 0, 0
    for i, j in zip(s, s[1:]):
        if i == j:
            ko += 1
        else:
            fuko += 1
    print(ko + min(k*2, fuko))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
N, K = MAP()
S = input()
cnt = 0
for i in range(1, N):
	if S[i] == S[i-1]:
		cnt += 1

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

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

cnt = 0

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

print(len(S)-1-cnt)

Submission status: Accepted

Solution code:
import itertools
N, K = map(int,input().split())
S = input()
##num = [i for i in range(1,N + 1)]
##for i in itertools.combinations(num, 2):
##    #print(i)
ans = 0
for i in range(1, N):
    if S[i] == S[i - 1]:
        ans += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

rl_cnt = 0
for s1,s2 in zip(s[:-1],s[1:]):
    if s1 == 'R' and s2 == 'L':
        rl_cnt += 1

left_happy = 1 if s[0] == 'R' else 0
right_happy = 1 if s[-1] == 'L' else 0

first_happy = n - rl_cnt*2 -2 + left_happy + right_happy
# print(first_happy)
if k <= rl_cnt:
    ans = first_happy + k*2
else:
    rem = k-rl_cnt
    ans = first_happy + rl_cnt*2 + min(rem, 2-left_happy+right_happy)

print(min(ans,n-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    n, k = 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)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# 解説配信の模範解答
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
ans = min(score + 2*K, N-1)
print(ans)

Submission status: Accepted

Solution code:
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
else:
    if K < gr//2:
        ans = hp + 2 * K
    else:
        ans = hp + 2 * ((gr-1) // 2) + (gr-1) % 2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
segs = []
prev = "x"
for c in S:
    if c != prev:
        segs.append([c])
    else:
        segs[-1].append(c)
    prev = c
ans = sum(len(seg) - 1 for seg in segs)
print(min(ans + 2 * K, N - 1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc140/tasks/abc140_d
n, k = map(int, input().split())

s = input()
block = 0
start = 0
seg = []
block = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        block += 1

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

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
print(min(happy+k*2,n-1))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    S = input()
    ret = 0
    for i in range(1,N-1):
        if (S[i]=='L' and S[i-1]=='L') or (S[i]=='R' and S[i+1]=='R'):
            ret += 1
    if S[0]=='R' and S[1]=='R':
        ret += 1
    if S[N-1]=='L' and S[N-2]=='L':
        ret += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
c = []
buf = 1
for i in range(n-1):
    if s[i]==s[i+1]:
        buf += 1
    else:
        c.append(buf)
        buf = 1
c.append(buf)
n = len(c)
l = min(n,2*k+1)
ans = buf = sum(c[:l])
ind = 0
for i in range(n-l):
    buf = buf-c[i]+c[i+l]
    if ans<buf:
        ind = i+1
        ans = buf
ans -= 1
for i in range(n):
    if ind<=i<ind+l:
        continue
    ans += c[i]-1
print(ans)