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:
N,K=(int(i) for i in input().split())
S=input()

p=0
m=0
ans=0
if S[0]=="R":
    m+=1
if S[0]=="L":
    p+=1
for i in range(N-1):
    if S[i]=="R" and S[i+1]=="L":
        p+=1
    elif S[i]=="L" and S[i+1]=="R":
        m+=1
    else:
        ans+=1
if S[N-1]=="R":
    m+=1
if S[N-1]=="L":
    p+=1
t=min(p,m)
ans+=min(t,K)*2
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

X = []
n_s = ''
start = None

for i, s in enumerate(S):
    if n_s == '':
        n_s = s
        start = i
        continue

    elif s == n_s:
        continue

    else:
        n_s = s
        end = i

        if (start == 0) or (i == N - 1):
            X.append(1)
        else:
            X.append(2)
        start = i
ans = 0
S = 'x' + S + 'x'
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

X.sort(reverse=True)
print(ans + sum(X[:K]))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())	
s=list(input())
a=0
b=0
c=0
for i in range(n-1):
    if(s[i]=="L" and s[i+1]=="R"):
        a+=1
    elif(s[i]=="R" and s[i+1]=="L"):
        b+=1
    else:
        c+=1
ans=c+min(a,b,k)*2
if( min(a,b,k)<k ):
    a-=min(a,b,k)
    b-=min(a,b,k)
    if((a==0 and b==1) or (a==1 and b==0)):
        ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
s=list(input())
ct=0
for i in range(n-1):
  if s[i]=='R' and s[i+1]=='L':ct+=1
if ct<=k:
  print(n-1)
  sys.exit()
ans=n-ct*2
ans+=2*k
if s[0]=='L':
  ans-=1
if s[n-2]=='L' and s[n-1]=='R':
  ans-=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import collections
sys.setrecursionlimit(4100000)

n, k = [int(i) for i in input().split()]
s = input()

ans = 0
for i,v in enumerate(s):
    if i == 0:
        continue
    if s[i] == s[i-1]:
        ans += 1
if ans >= n//k:
    print(n-1)
else:
    print(ans+k+k)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
S = list(input())
numL = S.count("L")
numR = S.count("R")

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

if K >= min(turning_l, turning_r):
	print(N-1)
else:
	print(score + 2*K)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())	
s=list(input())
a=0
b=0
c=0
for i in range(n-1):
    if(s[i]=="L" and s[i+1]=="R"):
        a+=1
    elif(s[i]=="R" and s[i+1]=="L"):
        b+=1
    else:
        c+=1
ans=c+min(a,b,k)*2
if( min(a,b,k)<k ):
    if((a==0 and b==1) or (a==1 and b==0)):
        ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = str(input())
L = []
R = []
now = "E"
ss = 0
for i in range(n):
    if s[i] != now:
        if s[i] == "R" and ss:
            L.append(ss)
        elif s[i] == "L" and ss:
            R.append(ss)
        ss = 1
        now = s[i]
    else:
        ss += 1
    if i == n-1:
        if s[i] == "R" and ss:
            R.append(ss)
        elif s[i] == "L" and ss:
            L.append(ss)
  # print(R,L)

ans = 0
for i in range(len(R)):
    ans += R[i]-1
for i in range(min(len(L),m)):
    ans += L[i]+1

an = 0
for i in range(len(L)):
    an += L[i]-1
for i in range(min(len(R),m)):
    an += R[i]+1
print(max(ans,an))

Submission status: Wrong Answer

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

l = 0
r = N - 1

k = 0
count = 0
while l < r:
	if k >= K:
		break
	d = S[l]
	while l < r and S[l] == S[l + 1]:
		count += 1
		l += 1
	l += 1
	while l < r and S[r] == d:
		count += 1
		r -= 1
	if r < N - 1:
		count += 2
	else:
		count += 1
	k += 1

while l < r:
	if S[l] == S[l + 1]:
		count += 1
	l += 1

print(count)

Submission status: Wrong Answer

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

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

start = s[0]
t = -1
for i in range(n):
    if s[i] != start:
        t += 1
    if t == 1 and k > 0:
        ans += 2
        t = -1
        k -= 1

if k > 0 and start != s[n-1]:
    ans += 1

print(ans)

Submission status: Wrong Answer

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

bef = s[0]
temp = 0

# if s[0] != "L":
#     comp.append(0)
#
# if s[-1] != "L":
#     comp.append(0)

for c in s:
    if c == bef:
        temp += 1
    else:
        comp.append(temp)
        temp = 1
        bef = c
comp.append(temp)
# print(comp)
#
# n = len(comp)
#
# leng = k*2 +1
#
# if leng >= n:
#     print("over")
#     print(sum(comp))
# else:
#     step = (n-leng)//2
#     now = 0
#     ans = 0
#     for i in range(leng):
#         now += comp[i]
#     ans = now
#     print(ans)
#     for i in range(step):
#         now -= (comp[i*2]+comp[i*2+1])
#         now += (comp[i*2+2]+comp[i*2+3])
#         if now > ans:
#             ans = now
#         print(ans)
#
#     print(ans)

init = 0
n = len(comp)
for c in comp:
    init += c-1

inside = 0
if n%2 == 0:
    inside = n//2-1
else:
    inside = n//2

outside = 0

if n%2 == 0:
    outside = n//2-1
else:
    outside = 0

tot = inside+outside

if k >= tot:
    print(sum(comp)-1)
elif k > inside:
    print(init+2*inside+outside)
else:
    print(init+2*k)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
S = list(input())
numL = S.count("L")
numR = S.count("R")

score = 0
turning = []
for i in range(1, N):
	if S[i-1] == S[i]:
		score += 1
	else:
		turning.append(i)

if K >= len(turning):
	print(N-1)
else:
	print(score + 2*K)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
s="x"+s+"x"
lr,rl=0,0
ans=0
for i in range(1,n+1):
  if s[i]=="L":
    if s[i-1]=="L":
      ans+=1
    if s[i+1]=="R":
      lr+=1
  else:
    if s[i+1]=="R":
      ans+=1
    elif s[i+1]=="L":
      rl+=1
if k<=min(lr,rl):
  ans+=2*k
else:
  k-=min(lr,rl)
  if k>=abs(lr-rl):
    ans+=abs(lr-rl)
  else:
    ans+=k
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
happy = 0
if s[0] == "R" and s[1] == "R":
    happy += 1
if s[n - 1] == "L" and s[n - 2] == "L":
    happy += 1
for i in range(1, n - 1):
    if s[i] == "L":
        if s[i - 1] == "L":
            happy += 1
    else:
        if s[i + 1] == "R":
            happy += 1
lr = 0
rl = 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
for i in range(k):
    if min(lr, rl) >= 1:
        happy += 2
        lr -= 1
        rl -= 1
    elif max(lr, rl) >= 1:
        happy += 1
        lr = max(lr - 1, 0)
        rl = max(rl - 1, 0)
print(happy)

Submission status: Wrong Answer

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



N,K = map(int, input().split())
Sn = str(input())
Rn = [1]
for i in range(1,N):
  if Sn[i] == Sn[i-1]:
    Rn[-1] += 1
  else:
    Rn.append(1)
Rn.sort(reverse=True)

if len(Rn) > 2*K:
  print(sum(Rn[0:2*K]))
else:
  print(N-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
import copy

def main():
  n,k=map(int,input().split())
  s=input()
  # maked group
  t=[]
  t.append(s[0])
  x=s[0]
  for i in range(1,n):
    if x!=s[i]:
      t.append(s[i])
      x=s[i]
  #print(t)
  
  j=0
  while j<k:
    if len(t)<=2:
      print(n-1)
      exit(0)
    t=copy.copy(t[2:])
    j+=1
    
  print(n-1-(len(t)-1))

  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

ori_num=0
turn_num=0
for i in range(N):
    if i>0:
        if S[i-1] =='L' and S[i] =='L':
            ori_num += 1
        if S[i-1] != S[i]:
            turn_num +=1
        
    if i<N-1:
        if S[i] =='R' and S[i+1] =='R':
            ori_num += 1
while K:
    if turn_num >1:
        turn_num -= 2
        K -= 1
        ori_num += 2
    elif turn_num ==1:
        ori_num +=1
        K=0
print(ori_num)

Submission status: Time Limit Exceeded

Solution code:
def evaluate(directions):
    ans = 0
    for i, d in enumerate(directions):
        if 0 <= i+d and i+d <= N-1:
            if directions[i] == directions[i+d]:
                ans += 1
    return ans

def find_lr(directions):
    N = len(directions)
    for i in range(1, N):
        if directions[i-1] != directions[i]:
            l = i
            break
    else:
        l = None
        return None, None
    
    for i in range(l+1, N):
        if directions[i-1] != directions[i]:
            r = i
            break
    else:
        r = N
    return l, r

def solve(directions):
    l, r = find_lr(directions)
    if l is None:
        return False
    else:
        if l is not None:
            for i in range(l, r):
                directions[i] *= -1
        return True 
    
N, K = map(int, input().split())
S = input()
directions = [1 if s=="R" else -1 for s in S]
for k in range(K):
    result = solve(directions)
    if result == False:
        break
    
print(evaluate(directions))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,K = (int(x) for x in input().split())
S = input()
count = []
d = deque(list(S))

now = d.popleft()
cum = 1
for i in range(len(S)-1):
    popped = d.popleft()
    if popped == now:
        cum += 1
    else:
        count.append(cum)
        now = popped
        cum = 1
count.append(cum)

if len(count) // 2 <= K:
    print(N-1)
else:
    m = 0
    for i in range(len(count)-2*K):
        if i == 0:
            c = sum(count[0:2*K+1]) - 1
            d = sum([j-1 for j in count[2*K+1:]])
        elif i == len(count) - 2*K + 1:
            c = sum(count[-(2*K+1):])
            d = sum([j-1 for j in count[0:-(2*K+1)]])
        else:
            c = sum(count[i:2*K+1+i]) - 1
            d1 = sum([j-1 for j in count[0:i]])
            d2 = sum([j-1 for j in count[2*K+1+i:]])
            d = d1 + d2
        m = max(m,c+d)
    print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,K = (int(x) for x in input().split())
S = input()
count = []
d = deque(list(S))

now = d.popleft()
cum = 1
for i in range(len(S)-1):
    popped = d.popleft()
    if popped == now:
        cum += 1
    else:
        count.append([now,cum])
        now = popped
        cum = 1
count.append([now,cum])

a = [x[0] for x in count]
if min(a.count('L'),a.count('R')) <= K:
    print(N-1)
else:
    b = [x[1] for x in count]
    m = 0
    for i in range(len(b)-2*K):
        if i == 0:
            c = sum(b[0:2*K+1]) - 1
            d = sum([j-1 for j in b[2*K+1:]])
        elif i == len(b) - 2*K + 1:
            c = sum(b[-(2*K+1):])
            d = sum([j-1 for j in b[0:-(2*K+1)]])
        else:
            c = sum(b[i:2*K+1+i]) - 1
            d1 = sum([j-1 for j in b[0:i]])
            d2 = sum([j-1 for j in b[2*K+1+i:]])
            d = d1 + d2
        m = max(m,c+d)
    print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k=map(int,input().split())
s=input()
snum=[]
now_si=""
now_sinum=0
for i in range(len(s)):
    if(now_si!=s[i]):
        now_si=s[i]
        snum.append(now_sinum)
        now_sinum=1
    else:
        now_sinum+=1
else:
    snum.append(now_sinum)
snum.pop(0)
#print(snum)

if(len(snum)<3):
    print(sum(snum)-1)
    sys.exit()

for i in range(k):
    min_threesum=9999999999999
    min_threesum_j=9999999999999

    for j in range(len(snum)-3,-1,-1):
        threesum=snum[j]+snum[j+1]+snum[j+2]
        if(threesum==3):
            snum[j]+=snum[j+1]+snum[j+2]
            snum.pop(j+1)
            snum.pop(j+1)
            break
        elif(min_threesum>threesum):
            min_threesum=threesum
            min_threesum_j=j
    else:
        snum[min_threesum_j]+=snum[min_threesum_j+1]+snum[min_threesum_j+2]
        snum.pop(min_threesum_j+1)
        snum.pop(min_threesum_j+1)

#    print(snum)
    if(len(snum)<3):
        print(sum(snum)-len(snum))
        sys.exit()


print(sum(snum)-len(snum))

Submission status: Time Limit Exceeded

Solution code:
import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    stemp = input()
    s = "R"
    s += stemp
    s += "L"

    unhappy_edge = 0

    if s[1] == "L":
        unhappy_edge += 1
    if s[-2] == "R":
        unhappy_edge += 1

    unhappy_pair = 0
    prev = s[1]
    for i in range(2, n + 1):
        current = s[i]
        if prev == "R" and current == "L":
            unhappy_pair += 1
        prev = current

    while k > 0:
        if unhappy_pair > 0:
            unhappy_pair -= 1
            k -= 1
        elif unhappy_edge == 2:
            unhappy_edge -= 1
            break

    print(n - unhappy_pair * 2 - unhappy_edge)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    streak = [[S[0], 1]]
    for i in range(1,N):
        if S[i] != S[i-1]:
            streak.append([S[i],1])
        else:
            streak[-1][1] += 1

    # print(streak)
    idx = streak.index(max(streak, key=lambda x:x[1]))

    for _ in range(K):
        if len(streak) == 1:
            break

        if len(streak) >= 3:
            if idx == 0 or idx == len(streak) - 1:
                idx = streak.index(max(streak[1:-1], key=lambda x:x[1]))

        new_direct = 'L' if streak[idx][0] == 'R' else 'R'
        max_streak = streak[idx][1]
        max_streak += streak[idx-1][1] if idx > 0 else 0
        max_streak += streak[idx+1][1] if idx + 1 < len(streak) else 0

        new_streak = []
        new_idx = 0

        if idx - 1 > 0:
            new_streak.extend(streak[:idx - 1])

        new_streak.append([new_direct,max_streak])
        new_idx = len(new_streak) -1

        if idx + 2 < len(streak):
            new_streak.extend(streak[idx + 2:])

        streak = new_streak
        idx = new_idx
        # print(streak, idx)

    ans = sum(map(lambda x: x[1] - 1, streak))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def calc_perm(s):
    return "R" * len(s) if s[0] == "L" else "L" * len(s)


def do_perm(s):
    ordered_queues = []
    curr = s[0]
    curr_count = 0
    begin_idx = 0
    for idx, c in enumerate(s):
        if c == curr:
            curr_count += 1
        else:
            ordered_queues.append((begin_idx, curr_count))
            curr = c
            begin_idx = idx
            curr_count = 1
    ordered_queues.append((begin_idx, curr_count))

    max_l = 0
    max_q = None
    for idx, q in enumerate(ordered_queues):
        b = ordered_queues[idx - 1][1] if idx > 0 else 0
        e = ordered_queues[idx + 1][1] if idx < len(ordered_queues) - 1 else 0
        l = b + q[1] + e
        if l > max_l:
            max_l, max_q = l, q

    s = (
        s[: max_q[0]]
        + calc_perm(s[max_q[0] : max_q[0] + max_q[1]])
        + s[max_q[0] + max_q[1] :]
    )

    return s


def count_happy(s):
    happy = 0
    prev = None
    for c in s:
        if c == prev:
            happy += 1
        prev = c
    return happy


_, k = [int(i) for i in input().split()]
s = input()

for _ in range(k):
    if "L" not in s or "R" not in s:
        print(len(s) - 1)
        sys.exit()
    s = do_perm(s)

print(count_happy(s))

Submission status: Time Limit Exceeded

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

happiness = 0

li = []
lamp = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        lamp += 1
    else:
        li.append(lamp)
        lamp = 1
li.append(lamp)

flag = False
num = 1
while k != 0:
    if len(li) == 2 and k > 0:
        print(n-1)
        quit()
    for i in range(1, len(li)-1):
        if li[i] == num:
            a = li[i-1] + li[i] + li[i+1]
            li[i-1:i+2] = [a]
            k -= 1
            flag = True
            break
        flag = False
    if flag == False:
        num += 1
    if len(li) == 2:
        break

for i in li:
    happiness += i-1

print(happiness)

Submission status: Time Limit Exceeded

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

happiness = 0


def exchange(num, loc):
    global s
    tmp = s[loc:loc+num+1]
    tmp = tmp[::-1]
    tmp = ['L' if x == 'R' else 'R' for x in tmp]
    s[loc:loc+num+1] = tmp

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

for i in range(n-1):
    if s[i] == 'R' and s[i+1] == 'L' or s[i] == 'L' and s[i+1] == 'R':
        turn += 1


s = 'X' + s + 'X'
s = list(s)
lamp = -1
while k != 0:
    lamp += 1
    if turn == 1:
        print(n-1)
        exit()
    for j in range(2, n-lamp-1):
        if s[j] == 'R' and s[j - 1] != 'R' and s[j + lamp] == 'R' and s[j + lamp + 1] != 'R':
            happiness += 2
            exchange(lamp, j)
            k -= 1
            turn -= 2
            break
        elif s[j] == 'L' and s[j - 1] != 'L' and s[j + lamp] == 'L' and s[j + lamp + 1] != 'R':
            happiness += 2
            exchange(lamp, j)
            k -= 1
            turn -= 2
            break
    if turn == 0:
        break

print(happiness)

Submission status: Time Limit Exceeded

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

happy_count = 0
pre = ''
for index, si in enumerate(list(s)):
  if index == 0:
    continue
  if list(s)[index - 1] == si:
    happy_count += 1

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

Submission status: Time Limit Exceeded

Solution code:
import re

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

content = input()
start = 0
end = 0

for i in range(k):
  lrPoint = content.find('LR')
  rlPoint = content.find('RL')
  if lrPoint < 0 and rlPoint < 0:
    break
  if lrPoint < rlPoint:
    start = lrPoint+1
    end = rlPoint
  else:
    start = rlPoint+1
    end = lrPoint

  content = list(content)
  tmp = content[start:end+1]
  tmp.reverse()
  for i in range(len(tmp)):
    if 'L' == tmp[i]:
      tmp[i] = 'R'
    else:
      tmp[i] = 'L'
  content[start:end+1] = tmp
  content = "".join(content)
 
count = 0

for i in range(len(list(content)) - 1):
  if content[i] == content[i+1]:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

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

for _ in range(K):
    if not (S.find("L")>=0 and S.find("R")>=0):
        break
    A = list((s,len(list(it))) for s, it in groupby(S))
    s0, _ = A[0]
    s1, l = A[1]
    A[1] = (s0, l)
    S = "".join(s*l for s, l in A)
print(N - len(list(groupby(S))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N, K = map(int, input().split())
S = [len(list(g)) for k, g in groupby(input())]
i = 0
while i < K and len(S) > 2:
    S.insert(0, S.pop(0) + S.pop(0) + S.pop(0))
    i += 1
if i < K and len(S) == 2:
    S.append(S.pop(0) + S.pop(0))
print(sum(S) - len(S))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

flag  = False
i = 0
count_s = 0
new_S = ''
previous_s = S[0]
while K != 0 and i != N:
    if previous_s == S[i]:
        count_s +=1
        if i+1 == N:
            flag =True
            new_S += non_search_s*count_s
    else:
        if previous_s == search_s:
            new_S += non_search_s*count_s
            K -= 1
        else:
            new_S += non_search_s*count_s
        previous_s = S[i]
        count_s = 1
    i += 1
if not flag:
    new_S += S[i-1:N]
#print(new_S)
'''
while K != 0 and idx != N:
    if S[idx] == search_s:
        if not continue_flag:
            continue_flag = True
        new_S += non_search_s
    else:
        if continue_flag:
            continue_flag = False
            K -= 1
            last_idx = idx
        new_S += S[idx]
    idx += 1
new_S += S[idx:N]
#print(new_S)
'''
count_s = 0
previous_s = new_S[0]
for i in range(1,N):
    if previous_s == new_S[i]:
        count_s +=1
    else:
        previous_s = new_S[i]
print(count_s)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

continue_flag = False
idx = 0
lst_idx =  -5
new_S = ''
while K != 0 and idx != N:
    if S[idx] == search_s:
        if not continue_flag:
            continue_flag = True
        new_S += non_search_s
    else:
        if continue_flag:
            continue_flag = False
            K -= 1
            last_idx = idx
        new_S += S[idx]
    idx += 1
new_S += S[idx:N]
#print(new_S)

count_s = 0
previous_s = new_S[0]
for i in range(1,N):
    if previous_s == new_S[i]:
        count_s +=1
    else:
        previous_s = new_S[i]
print(count_s)

Submission status: Time Limit Exceeded

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


def flip_direction(target, start, end):
    for i in range(start, end + 1):
        if target[i] == 'R':
            target = target[:i] + 'L' + target[i + 1:]
            # S[i] = 'L'
        else:
            target = target[:i] + 'R' + target[i + 1:]
            # S[i] = 'R'
    return target


def count_happy_person():
    count = 0
    dir = S[0]
    for i in range(1, len(S)):
        if dir == S[i]:
            count += 1
        else:
            dir = S[i]
    return count


for _ in range(K):
    start = 0
    end = 0
    for i in range(1, len(S)):
        if S[0] != S[i]:
            if start == 0:
                start = i
            end = i
        else:
            if start != 0:
                break
    S = flip_direction(S, start, end)
print(count_happy_person())

Submission status: Time Limit Exceeded

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

def eval(N,S):
    total=0
    for i in range(1,N):
        if S[i]==S[i-1]:total+=1
    return total


for k in range(K):
    if S==['R']*N or S==['L']*N:break
    j=[]
    for i in range(1, N):
        if S[i-1]!=S[i]:
            j.append(i)
            if len(j)==2:break
    if len(j)==1:j.append(N)
    if S[j[0]]=='R':
        S[j[0]:j[1]]=['L']*(j[1]-j[0])
    else:S[j[0]:j[1]]=['R']*(j[1]-j[0])
print(eval(N,S))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
def get_num(S):
    enc =  {"L":1,"R":-1}
    res = 0
    for n in range(len(S)-1):
        if enc[S[n+1]]*enc[S[n]] == 1:
            res += 1
    return res
result = 0
rev = {"L":"R","R":"L"}
max_S = ""
for k in range(K):
    for l in range(N):
        for r in range(l, N):
            new_S = S[:l]
            t = S[l:r]
            for n in range(len(t)):
                new_S += rev[t[-n]]
            new_S += S[r:]
            m = get_num(new_S)
            if m > result:
                result = m
                max_S = new_S
                # print("-"*5)
                # print(new_S)
                # print(l, r)
                # print(result)
    S = max_S
print(result)

Submission status: Time Limit Exceeded

Solution code:
# 目の前の人が同じ方を向いてたら幸福
# 操作はK回以下
# l~rの範囲内を列の塊ごと反転

n, k = map(int, input().split())
s = list(input())
# R = True, L = False
b = []
for i in range(n):
    if s[i] == 'R':
        b.append(True)
    else:
        b.append(False)

# s[i] != s[i+1] となる最小のiをまず見つけて
# s[i] == s[j] となるiより大きい最小のjを見つけて
# s[i+1]~s[j-1] の区間をひっくり返す
# 通常2点増えるのに対し端を含むと1点しか増えないので後回しにする

for i in range(n-2):
    if b[i] == b[i+1]:
        continue

    for j in range(i+2, n):
        if b[i] == b[j]:
            mir = list(map(lambda x: not x, b[j-1:i:-1]))
            b = b[:i+1]+mir+b[j:]
            k -= 1
            break

    if k == 0:
        break

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

# 端を含む操作は1回行えば十分なので両端が異なる&kが余ってたら+1点
if k > 0 and b[0] != b[n-1]:
    happy += 1

print(happy)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc140/tasks/abc140_d

n, k = map(int, input().split())
str_n = input()
changed_str = [str_n]
left = ""
right = ""

if str_n[0] == "R":
    left = "RL"
    right = "LR"
else:
    left = "LR"
    right = "RL"

for count in range(k): 
    ew_line = changed_str[count]
    first = ew_line.find(left)
    last = ew_line.rfind(right) or -1
    change_count = last - first

       
    head = ew_line[:first + 1]
    body = ""
    foot = ""
    if last != -1:
        body = ew_line[first + 1:last + 1][::-1]
        foot = ew_line[last + 1:]
    else:
        body = ew_line[first + 1:]
    
    body = body.replace("R","C").replace("L","R").replace("C","L")

    new_line = head + body + foot
    changed_str.append(new_line)

# print(changed_str[k])
count = 0
result_line = changed_str[k]
for i in range(len(changed_str[k]) - 1):
    if result_line[i] == result_line[i + 1]:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# D - Face Produces Unhappiness

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
S = input()
prev_c = None
s_compressed = ""
score = 0
for c in S:
    if c != prev_c:
        s_compressed += c
    else:
        # 初期スコアを出す
        score += 1

    prev_c = c

if len(s_compressed) == 1:
    print(N - 1)
    quit()
else:
    score += 2 * K

print(min((N - 1, score)))

Submission status: Time Limit Exceeded

Solution code:
t = list(map(int, input().split())); n, k = t[0], t[1];
stripe = str(input());
def oper(stripe, p1, p2):
    cut = stripe[p1:p2+1]
    cut = cut[::-1]
    cut = list(cut)
    for i in range(len(cut)):
        if cut[i] == 'R':
            cut[i] = 'L'
        else:
            cut[i] = 'R'
    t = ''
    for thng in cut:
        t = t + thng
    cut = t
    stripe2 = stripe[:p1]
    stripe2 = stripe2 + cut
    stripe2 = stripe2 + stripe[p2+1:len(stripe)]
    return stripe2
stripe2 = stripe
stripe = list(stripe)
what = 0
while k != 0:
    for i in range(1, len(stripe)):
        for j in range(len(stripe)-1):
            if stripe2[i] == 'R' and stripe2[j] == 'R' and j>=i and stripe2[i-1] == 'L' and stripe2[j+1] == 'L':
                stripe2 = oper(stripe2, i, j); what = 1
                break
            elif stripe2[i] == 'L' and stripe2[j] == 'L' and j>=i and stripe2[i-1] == 'R' and stripe2[j+1] == 'R':
                stripe2 = oper(stripe2, i, j); what = 1
                break
        if what == 1:
            break
    if what == 0 and k >= 1 and stripe2[0] != stripe2[len(stripe2)-1]:
        print(n-1)
        break
    if what == 1:
        k = k - 1
        what = 0
    if k == 0:
        ea = 0
        stripe2 = list(stripe2)
        for i in range(1, len(stripe2)):
            if stripe2[i] == 'L' and stripe2[i-1] == 'L':
                ea += 1
        for j in range(len(stripe2)-1):
            if stripe2[j] == 'R' and stripe2[j+1] == 'R':
                ea += 1
        print(ea)
        break

Submission status: Time Limit Exceeded

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

def happy(n):
	h=0
	for  i in range(len(n)-1):
		if n[i]==n[i+1]:
			h+=1

	return h

def cange(n,l,r):
	x=n[:l-1]
	y=n[r:]
	r=n[l-1:r]
	r.reverse()
	_R=[]
	for i in r:
		if i=="L":
			_R.append("R")
		else:
			_R.append("L")

	x.extend(_R)
	x.extend(y)
	return x

MAX=[0]
old=[happy(S),0,0]
for T in range(K):
	for l in range(1,N+1):
		for r in range(l,N+1):
			hpp=happy(cange(S,l,r))
			if hpp>=old[0]:
				old=[hpp,l,r]

	S=cange(S,old[1],old[2])

print(old[0])