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: Wrong Answer

Solution code:
from itertools import groupby

n,k = map(int,input().split())
s = [0] + list(input())
print(s)
count_L = 0
count_R = 0
ans = 0
for i in range(1,n):#調べる対象はs[2]からs[n-1]まで
    if s[i-1] == 'R' and s[i] == 'L' and s[i+1] == 'R':
        count_L += 1
    elif s[i-1] == 'L' and s[i] == 'R' and s[i+1] == 'L':
        count_R += 1
    elif s[i-1] == 'R' and s[i] == 'R':
        ans += 1
    elif s[i-1] == 'L' and s[i] == 'L':
        ans += 1
count_max = max(count_L,count_R)
print(count_max,ans)

if count_max >= k:
    ans = ans + 2*k
else:
    ans = ans + 2*count_max + 1

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,K= map(int,input().split())
S = list(input())
ans = 0
flag = 0
num = 0
while num < K:
  for i in range(0,n-3):
    if num == K:
      break
    for j in range(i+2,n-1):
      if num == K:
        break
      if S[i] != S[i+1] and S[j] != S[j+1] and S[i] != S[j]:
        num += 1    
        ans += 2
    
  if num == K :
    break
  a = S.count("L")
  if K-num > abs(n - 2*a):
    ans +=  K-num
    break
  else:
    ans += abs(n-2*a)
    break
        
    
for i in range(n-1):
  if S[i] == S[i+1]:
    ans += 1
        
print(ans)

Submission status: Wrong Answer

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

left_ac = [0]
right_ac = [0]

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

left = 0
right = 0
ans = right_ac[-1] + left_ac[-1]
remain = K

if left_ac[-1] == 0 and right_ac[-1] == 0:
    if K==0:
        print(0)
        exit()
while left < N:
    s = S[left]
    while remain > 0 and right < N:
        if S[right] != s:
            if (right + 1 < N and S[right + 1] == s) or (right == N - 1 and S[N - 1] != s):
                remain -= 1
        right += 1

    if s == "L":
        tmp = right - left
        if right == N:
            tmp -= 1
        if right <= N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)
    else:
        tmp = right - left
        if right == N:
            tmp -= 1
        if right <= N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)

    if right == left:
        right += 1
    if left + 1 < N and S[left + 1] != s:
        remain += 1
    left += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
s = list(input())
if s[0] == 'L':
    s.insert(0, 'R')
else:
    s.insert(0, 'L')

if s[N] == 'L':
    s.append('R')
else:
    s.append('L')

for _ in range(K):
    t = s.copy()
    for i in range(0, N+1):
        if s[i] != s[i+1]:
            start = i+1
    for i in range(N+1, 0, -1):
        if s[i] != s[i-1]:
            end = i-1
    if end <= start:
        break
    for i in range(end-start+1):
        if t[start+i] == 'L':
            s[end-i] = 'R'
        else:
            s[end-i] = 'L'
    if s[1] == 'L':
        s[0] = 'R'
    else:
        s[0] = 'L'
    if s[N] == 'L':
        s[N+1] = 'R'
    else:
        s[N+1] = 'L'

count = 0
for i in range(1, N):
    if s[i] == s[i+1]:
        count = count + 1

print(count)

Submission status: Wrong Answer

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

RL_count=s.count("RL")
LR_count=s.count("LR")
term_count=0
if s[0]=="L":
    term_count+=1
if s[n-1]=="R":
    term_count+=1

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

if RL_count!=1:
    if k>RL_count:
        ans+=2*RL_count
        if LR_count>=1:
            ans+=1
        if LR_count==2 and k>RL_count+1:
            ans+=1
    else:
        ans+=2*k
else:
    if LR_count >= 1:
        ans += 1
    if LR_count == 2 and k > 1:
            ans += 1
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
s = input()


def split(s):
    last = ''
    new = []
    for x in s:
        if last != x:
            new.append(x)
        else:
            new[-1] += x
        last = x
    return new


def transform(s, k):

    s = split(s)
    for _ in range(k):
        if len(s) == 1:
            break
        # これが重そう
        ls = list(map(len, s))
        idx = ls.index(min(ls))
        if idx == 0:
            idx = ls[1:].index(min(ls[1:]))+1

        # print(s, idx, ls)
        s[idx] = s[idx].replace('L', 'X').replace('R', 'L').replace('X', 'R')
    s = ''.join(s)
    # print(s)
    return s


s = transform(s, k)


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


print(count(s))

Submission status: Wrong Answer

Solution code:

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

def reverse(S, l=0, r=n-1):
    for i in range(l, (l+r)//2+1):
        S[i], S[r+l-i] = int(not S[r+l-i]), int(not S[i])

def happiness(S):
    point = 0
    neighbor = -1
    for s in S:
        if s == neighbor:
            point += 1
        neighbor = s
    return point


def main():
    global k

    S = list(map(lambda s: int(s=='L'), input()))

    answers = []
    plus_one = []
    plus_two = []
    for l in range(n):
        for r in range(n-1, l-1, -1):
            point = 0
            if l == 0 and r == n-1:
                    break
            elif l == 0:
                if int(not S[l]) == S[r+1]:
                    point += 1
            elif r == n - 1:
                if int(not S[r]) == S[l-1]:
                    point += 1
            else:
                if int(not S[l]) == S[r+1]:
                    point += 1
                if int(not S[r]) == S[l-1]:
                    point += 1
            if point == 1:
                plus_one.append((l, r))
            elif point == 2:
                plus_two.append((l, r))

    while k > 0:
        for two in plus_two:
            if k == 0:
                break
            reverse(S, two[0], two[1])
            k -= 1
        for one in plus_two:
            if k == 0:
                break
            reverse(S, one[0], one[1])
            k -= 1
    print(happiness(S))


main()

Submission status: Wrong Answer

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

count = 1
for i in range(1, n):
    if s[i] == s[i-1]:
        count += 1
    else:
        if s[i-1] == "L":
            a.append(count)
        else:
            b.append(count)
        count = 1
if n == 1:
    i = 0
if s[i] == "L":
    a.append(count)
else:
    b.append(count)
count = 1

a.sort(reverse=True)
b.sort(reverse=True)
ans1 = sum(a) - len(a)
ans2 = sum(b) - len(b)
for i in range(min(2*k, len(b))):
    ans1 += b[i]
if len(b) <= 2*k:
    l = len(b)
    if (2*k - l) % 2 == 1:
        ans1 += (2*k - l)
    else:
        ans1 += (2*k - l) + 2
ans1 = min(n-1, ans1)
for i in range(min(2*k, len(a))):
    ans2 += a[i]
if len(a) <= 2*k:
    l = len(a)
    if (2*k - l) % 2 == 1:
        ans2 += (2*k - l)
    else:
        ans2 += (2*k - l) + 2
ans2 = min(n-1, ans2)
ans = max(ans1, ans2)
if ans1 != ans2:
    ans = min(ans1, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
S = (stdin.readline().rstrip())
ans = 0
no = 0
for i in range(0,N-1):
    if S[i] == S[i+1]:
        ans += 1
    else:
        no += 1
if no == 1:
   ans += 1
else:
   ans += (min(no,K)*2)
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC140d
import re
import sys
import time
start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
s = input()[:-1]


findings = re.findall('R+|L+', s)
score = [0]*len(findings)
for i in range(len(score)):
    score[i] = len(findings[i])
# print(score)

for _ in range(k):
    superscore = [0] * len(score)
    maxScore = 0
    maxScorePos = 0
    for i in range(len(score)):
        superscore[i] = score[i]
        if (i - 1 >= 0):
            superscore[i] += score[i - 1]
        if (i + 1 < len(score)):
            superscore[i] += score[i+1]
    # print('superscore'+str(superscore))
    center = superscore.index(max(superscore))
    tempscore = score[center]
    if (center - 1 >= 0):
        tempscore += score[center - 1]
    if (center + 1 < len(score)):
        tempscore += score[center+1]
    score[max(0, center-1):min(len(score), center+2)] = [tempscore]
    # print(score)
    #print(time.time() - start)
    if (time.time() - start > 1.9):
        break

print(sum(score)-len(score))

Submission status: Wrong Answer

Solution code:
import sys

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

shiawase = 0
# 幸せカウント
for i in range(N-1):
    if S[i] == S[i+1]:
        shiawase += 1


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

# N >= 2
left = 0
right = N-2

count = [0, 0]
hanten = 0

# for i in range(K + 2):
while K > 0:
    # left, right をすすめる
    while left < N-1 and S[left] == S[left+1]:
        left += 1
        if S[left] == "L":
            count[hanten] += 1
        else:
            count[1 - hanten] += 1
    while right >= 0 and S[right] == S[right+1]:
        right -= 1
        if S[left] == "R":
            count[hanten] += 1
        else:
            count[1 - hanten] += 1

    if left >= right:
        break

    shiawase += 2

    K -= 1
    hanten = 1 - hanten

shiawase += min(K, *count)


print(shiawase)

Submission status: Wrong Answer

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

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

count=0
for i in range(1,n//2+1):
  if count==k:
    break
  if s[i-1]==s[i+1] and s[i]!=s[i-1]:
    s[i]=s[i-1]
    count+=1

  if count==k:
    break
  if s[n-i]==s[n-i-2] and s[n-i-1]!=s[n-i]:
    s[n-i-1]=s[n-i]
    count+=1

result=0
if count!=k and s[0]=='L':
  for i in range(1,n):
    if s[i-1]!=s[i]:
      result+=1
      count+=1
      break
    if count==k:
      break
      
if count!=k and s[-1]=='R':
  for i in range(1,n):
    if s[n-i-1]!=s[n-i]:
      result+=1
      count+=1
      break
    if count==k:
      break
    
if s[0]=='R' and s[1]=='R':
  result+=1
if s[-1]=='L' and s[-2]=='L':
  result+=1
for i in range(1,n-1):
  if (s[i]=='R' and s[i+1]=='R') or (s[i]=='L' and s[i-1]=='L'):
    result+=1
print(result)

Submission status: Wrong Answer

Solution code:
n,k = map(int,raw_input().split())
s = raw_input()
Llist = []
Rlist = []
cur = 0
for i in xrange(n-1,-1,-1):
	if s[i] == 'L':
		cur += 1
	else:
		if cur > 0:
			Llist.append(cur+1)
			cur = 0
if cur > 0:
	Llist.append(cur)
for i in xrange(1,n):
	if s[i] == 'R':
		cur += 1
	else:
		if cur > 0:
			Rlist.append(cur)
			cur = 0
if cur > 0:
	Rlist.append(cur)
#print Llist
#print Rlist
Lh = 0
Rh = 0
for i in xrange(1,n):
	if s[i] == 'L' and s[i-1] == 'L':
		Lh += 1
for i in xrange(0,n-1):
	if s[i] == 'R' and s[i-1] == 'R':
		Rh += 1

Llist = sorted(Llist, reverse=True)
Rlist = sorted(Rlist, reverse=True)
#print Lh,Rh

print max(Rh+sum(Llist[0:k]),Lh+sum(Rlist[0:k]))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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


v = Counter(S)
d, _  = v.most_common()[0]

# R, L
# def search(c1, c2):
#     first = False
#
#     for i in range(1, N):
#         if not first and S[i - 1] == c1 and S[i] == c2:
#             S[i] = c1
#             first = True


def search(c1, c2):
    ret1 = 0
    ret2 = 0

    cnt = 0
    for i in range(1, N):
        if S[i - 1] == c1 and S[i] == c2:
            ret1 += 1
        elif S[i - 1] == c2 and S[i] == c1:
            ret2 += 1

        if S[i - 1] == S[i]:
            cnt += 1

    return ret1, ret2, cnt


if d == 'R':
    r1, r2, cnt = search('L', 'R')
else:
    r1, r2, cnt = search('R', 'L')


if r1 == 0 or r2 == 0:
    print(N - 1)
else:
    print(cnt + min(min(r1, r2), K) * 2)

Submission status: Wrong Answer

Solution code:
N, K=map(int, input().split())
S=input()
A=[]
tmp=1
for i in range(1,N):
    if S[i-1]==S[i]:
        tmp+=1
    else:
        A.append(tmp)
        tmp=1
A.append(tmp)

while K>0:
    #print(A)
    K-=1
    tmpmax=0
    tmpindex=0
    if len(A)>2:
        for i in range(1,len(A)-1):
            tmp=A[i-1]+A[i]+A[i+1]
            if tmp>tmpmax:
                tmpindex=i
                tmpmax=tmp
        A[tmpindex]=tmpmax
        A.pop(tmpindex-1)
        A.pop(tmpindex)
    else:
        break
        
if len(A)>=2 and K==0:
    print(sum(A)-len(A))
else:
    print(N-1)

Submission status: Wrong Answer

Solution code:
# ABC140d
import re
import sys
import time
start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
s = input()[:-1]


findings = re.findall('R+|L+', s)
score = [0]*len(findings)
for i in range(len(score)):
    score[i] = len(findings[i])
# print(score)

for _ in range(k):
    superscore = [0] * len(score)
    maxScore = 0
    maxScorePos = 0
    for i in range(len(score)):
        superscore[i] = score[i]
        if (i - 1 >= 0):
            superscore[i] += score[i - 1]
        if (i + 1 < len(score)):
            superscore[i] += score[i+1]
    # print('superscore'+str(superscore))
    center = superscore.index(max(superscore))
    tempscore = score[center]
    if (center - 1 >= 0):
        tempscore += score[center - 1]
    if (center + 1 < len(score)):
        tempscore += score[center+1]
    score[max(0, center-1):min(len(score), center+2)] = [tempscore]
    # print(score)
    #print(time.time() - start)
    if (time.time() - start > 1.8):
        break

print(sum(score)-len(score))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin.readline
na = lambda: map(int, stdin().split())
ns = lambda: stdin().rstrip()
ni = lambda: int(ns())
def main():
  n, k = na()
  s = ns()+"0"

  ans = 0
  LRcnt = []
  cnt = 1
  LR = []
  for i in range(n):
    if s[i] == s[i+1]:
      ans += 1
      cnt += 1
    else:
      LR.append(s[i])
      LRcnt.append(cnt)
      cnt = 1

  N = len(LRcnt)
  wa = [0] * (N+1)
  for i in range(N):
    wa[i+1] = wa[i] + LRcnt[i]

  ans = 0
  for i in range(N-k-2):
    x = wa[i+k+2] - wa[i] - 1 + sum(LRcnt[i+k+2:]) - len(LRcnt[i+k+2:]) + sum(LRcnt[:i+k+2]) - len(LRcnt[:i+k+2])
    if ans < x:
      ans = x
      if LR[i] == "R":
        ans -= 1

  if ans == 0:
    print(sum(LRcnt)-1)
  else:
    print(ans)
main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

left_ac = [0]
right_ac = [0]

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

left = 0
right = 0
ans = right_ac[-1] + left_ac[-1]
remain = K

if left_ac[-1] == 0 and right_ac[-1] == 0:
    if K==0:
        print(0)
        exit()
while left < N:
    s = S[left]
    while remain > 0 and right < N:
        if S[right] != s:
            if (right + 1 < N and S[right + 1] == s) or (right == N - 1 and S[N - 1] != s):
                remain -= 1
        right += 1

    if s == "L":
        print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right <= N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)
    else:
        print(s, right - left, left, right)
        tmp = right - left
        if right == N:
            tmp -= 1
        if right <= N - 1:
            tmp += right_ac[-1] - right_ac[right]
            tmp += left_ac[-1] - left_ac[right]
        if left > 0:
            tmp += left_ac[left - 1] - left_ac[0]
            tmp += right_ac[left - 1] - right_ac[0]
        ans = max(ans, tmp)

    if right == left:
        right += 1
    if left + 1 < N and S[left + 1] != s:
        remain += 1
    left += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = list(input())
lc = s.count('L')
rc = s.count('R')
while k > 0:
    for i in range(n):
        if i == n-1:
            break
        if lc > rc:
            _ = 'L'
        else:
            _ = 'R'
        if s[i] == _ and s[(n-1)-i] == _:
            continue
        s[i], s[(n-1)-i] = s[(n-1)-i], s[i]
        if s[i] == 'L':
            s[i] = 'R'
        else:
            s[i] = 'L'
        if s[(n-1)-i] == 'L':
            s[(n-1)-i] = 'R'
        else:
            s[(n-1)-i] = 'L'
        k -= 1
        if k == 0:
            break
pt = 0
for i in range(n):
    if i != n-1:
        if s[i] == s[i+1]:
            pt += 1
print(pt)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
mod = 10**9 + 7

import numpy as np

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, k = na()
s = ns()
t = [0]
if s[0] == "L":
        t.append(0)
t.append(1)
for i in range(1, n):
        if s[i] == s[i-1]:
                t[-1] +=1
        else:
                t.append(1)
for i in range(3 * k):
        t.append(0)
size = len(t)
s = [0] * size
for i in range(1, size):
        s[i] = s[i-1] + t[i]
# print(t)
# print(s)
# print(k, size)
ans = 0
for i in range(1, size, 2):
        if (i + 2*k) >= size:
                break
        ans = max(ans, s[i + 2*k] - s[i-1])
print(ans)

Submission status: Wrong Answer

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

happiness = 0
cnt = 0
if N == 1:
    print(0)
elif N == 2:
    print(1)
else:
    if S[1] == S[0]:
        happiness += 1
    for i in range(2,N):
        if cnt < K and S[i] == S[i-2] and S[i] != S[i-1]:
            happiness += 2
            S[i-1] = S[i]
            cnt += 1
        elif S[i] == S[i-1]:
            happiness += 1
    if cnt < K:
        happiness += 1
    print(happiness)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
#LR数できまる.
#両側が同じときはさらにもう一つ減る
LR = 0

for j in range(N-1):
    if S[j] == "L" and S[j+1]== "R":
        LR += 1

if LR > K:
    ans = N - (LR-K)*2
else:
    ans = N

if S[0] == S[-1]:
    ans -= 1

RL = 0

for j in range(N-1):
    if S[j] == "R" and S[j+1]== "L":
        RL += 1

if RL > K:
    ans2 = N - (RL-K)*2
else:
    ans2 = N

if S[0] == S[-1]:
    ans2 -= 1

if ans2 > ans:
    print(ans)
else:
    print(ans2)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
S = list(input())
a = S[0]
cur = 0
cnt = 0
for i in range(N):
    if S[i] != a:
        cnt += i-cur-1
        a = S[i]
        cur = i
if S[N-1]==a:
    cnt += N-cur-1
print(min(cnt+2*K,N))

Submission status: Wrong Answer

Solution code:
temp = raw_input().split()
S = raw_input()

N = int(temp[0])
K = int(temp[1])

ini_score = 0
ex_count = 0


S = list(S)

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

num_double_interface = 0
for i in range(1,N-1):
    if (S[i] != S[i-1]) and (S[i]!= S[i+1]):
#        print i, "double"                                                                                                                              
        if S[i] == "L":
            S[i] = "R"
        else:
            S[i] = "L"
        num_double_interface = num_double_interface + 1
        ex_count = ex_count + 1

    if ex_count==K:
        print ini_score + 2*num_double_interface
        exit()



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


current_score = ini_score + 2*num_double_interface
max_score = N-1

remaining = K - ex_count

if num_single_interface == 1:
    print max_score
    exit()
if num_single_interface - 1 > remaining:
    best_score = ini_score + 2*num_double_interface + 2*(K-ex_count)
else:
    print max_score
    exit()

Submission status: Wrong Answer

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

def set_list(es):
    return len(list(set(es))) == 1

double = 0
single =0
s0 = s[0]

i = 1
while i<n:
    print(i)
    if k==0:
        break
    if s0 == s[i]:
        i += 1
    else:
        si = s[i]
        ll = s[i+1:]
        if set_list(ll):
            i += 1
            single+=1
            break
        else:
            double+=1
            for sj in ll:
                i+=1
                if si!=sj:
                    k -= 1
                    break
                
c = len([i for i in range(n-1) if s[i]==s[i+1]])
print(c+double*2+single)

Submission status: Wrong Answer

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

counts = []

cnt = 1
for i in range(len(S)-1):
  if (S[i] == S[i+1]):
    cnt += 1
  else:
    counts.append(cnt)
    cnt = 1
  if (i == len(S)-2 and cnt > 1):
    counts.append(cnt)
counts.sort(reverse=True)
if (sum(counts) == N):
  print(N-1)
else:
  print(sum(counts[0:K]) + K)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

  while k > 0:
      if count > 1:
          ans += 2
          count -= 2
      elif count == 1:
          ans += 1
          count -= 1
      k -= 1
  print(ans)

Submission status: Wrong Answer

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

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

if K < cnt:
  score += 2*K
else:
  score += 2*cnt

print(score-1)

Submission status: Wrong Answer

Solution code:
import sys
#input=sys.stdin.readline
sys.setrecursionlimit(3000)


#L=-1  R=1
n,k=map(int,input().split())
s=input()
#print(s)
t=s[0]
c=[-1,1][s[0]=="R"]
d=[0]

for i in range(1,n):
    if t!=s[i]:
        d.append(c)
        c=0
    t=s[i]
    c+=[-1,1][s[i]=="R"]
d.append(c)
c=len(d)

#print(d)
p=[-1,-1]
for i in range(1,c-1):
    tmp=(abs(d[i-1])+abs(d[i])+abs(d[i+1]))
    if tmp>p[0]:
        p[0]=tmp
        p[1]=i
i=p[1]
for j in range(k):
    if i+j*2>=c: break
    d[i+j*2]*=-1
chk=0
ans=0
for i in d:
    if (i>0 and chk>0) or (i<0 and chk<0):
        chk+=i
    else:
        if chk!=0: ans+=abs(chk)-1
        chk=i

print(ans+(abs(chk)-1))

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N, K = [int(x) for x in input().split()]
    S = list(input())
    ans = 0
    old = S[0]
    temp = deque(S)
    check = deque(maxlen=K*2)
    count = 0
    while temp:
        x = temp.popleft()
        if old == x:
            count += 1
        else:
            check.append(count)
            n = sum(check)
            if n > ans:
                ans = n
            count = 1
            old = x
            
    check.append(count)
    n = sum(check)
    if n > ans:
        ans = n
    print(n)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
s = input()


def split(s):
    last = ''
    new = []
    for x in s:
        if last != x:
            new.append(x)
        else:
            new[-1] += x
        last = x
    return new


def transform(s, k):

    for _ in range(k):
        s = split(s)
        if len(s) == 1:
            break
        ls = list(map(len, s))
        idx = ls.index(min(ls))
        if idx == 0:
            idx = ls[1:].index(min(ls[1:]))+1

        # print(s, idx, ls)
        s[idx] = s[idx].replace('L', 'X').replace('R', 'L').replace('X', 'R')
        s = ''.join(s)
    # print(s)
    return s


s = transform(s, k)


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


print(count(s))

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
lst = list(input())
dif = []
for i in range(n):
    if lst[i]=="L":
        lst[i]=1
    else:
        lst[i]=-1
for i in range(n-1):
    dif.append(lst[i]-lst[i+1])

pos=dif.count(2)
neg=dif.count(-2)
zero = dif.count(0)
if min(pos,neg)>k:
    print(zero+k*2)
else:
    print(zero+min(pos,neg)+k)

Submission status: Wrong Answer

Solution code:
import sys

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

shiawase = 0
# 幸せカウント
for i in range(N-1):
    if S[i] == S[i+1]:
        shiawase += 1


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

# N >= 2
left = 0
right = N-2

count = [0, 0]
hanten = 0

# for i in range(K + 2):
while K > 0:
    # left, right をすすめる
    while left < N-1 and S[left] == S[left+1]:
        left += 1
        if S[left] == "L":
            count[hanten] += 1
        else:
            count[1 - hanten] += 1
    while right >= 0 and S[right] == S[right+1]:
        right -= 1
        if S[left] == "R":
            count[hanten] += 1
        else:
            count[1 - hanten] += 1

    if left >= right:
        break

    shiawase += 2

    left += 1
    right -= 1

    K -= 1
    hanten = 1 - hanten

shiawase += min(K, *count)


print(shiawase)

Submission status: Wrong Answer

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

count = 1
for i in range(1, n):
    if s[i] == s[i-1]:
        count += 1
    else:
        if s[i-1] == "L":
            a.append(count)
        else:
            b.append(count)
        count = 1
if n == 1:
    i = 0
if s[i] == "L":
    a.append(count)
else:
    b.append(count)
count = 1

a.sort(reverse=True)
b.sort(reverse=True)
ans1 = sum(a) - len(a)
ans2 = sum(b) - len(b)
for i in range(min(2*k, len(b))):
    ans1 += b[i]
if len(b) <= 2*k:
    l = len(b)
    if (2*k - l) % 2 == 1:
        ans1 += (2*k - l)
    else:
        ans1 += (2*k - l)
ans1 = min(n-1, ans1)
for i in range(min(2*k, len(a))):
    ans2 += a[i]
if len(a) <= 2*k:
    l = len(a)
    if (2*k - l) % 2 == 1:
        ans2 += (2*k - l)
    else:
        ans2 += (2*k - l) - 1
ans2 = min(n-1, ans2)
ans = max(ans1, ans2)
if ans1 != ans2:
    ans = min(ans1, ans2)
print(ans)