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: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
s = input()
s = s.replace('LR', 'L,R')
s = s.replace('RL', 'R,L')
s = s.split(',')
s = list(map(len, s))
l = 2*k+1
ans = -1

s_ = list(np.array(s) - 1)
if l >= len(s):
    ans = sum(s)-1
else:
    
    for i in range(len(s)-l+1):
        cnt = 0
        cnt += sum(s_[:i])
        cnt += sum(s[i:l+i])-1
        cnt += sum(s_[l+i:])
        ans = max(ans, cnt)   
print(ans)

Submission status: Time Limit Exceeded

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

def f1(s, l, r):
  return s[:l] + f2(s[l:r + 1]) + s[r + 1:]

def f2(s):
  t = list(s)
  t.reverse()
  return ''.join('R' if c == 'L' else 'L' for c in t)

def f3(s):
  before = s[0]
  result = 0
  for i in range(1, N):
    if s[i] == before:
      result += 1
    else:
       before = s[i]
  return result

def f4(s, c):
  lstart = -1
  llen = 0
  tstart = -1
  for i in range(N):
    if s[i] == c and tstart == -1:
      tstart = i
    if s[i] != c and tstart != -1:
      tlen = i - tstart
      if tlen > llen:
        lstart = tstart
        llen = tlen
      tstart = -1
  if tstart != -1:
    tlen = N - tstart
    if tlen > llen:
      lstart = tstart
      llen = tlen
  return (lstart, llen)

for _ in range(K):
  lstart, llen = f4(S, 'L')
  #print('X', lstart, llen)
  rstart, rlen = f4(S, 'R')
  #print('Y', rstart, rlen)
  if lstart == -1 or rstart == -1:
    break
  if lstart < rstart:
    #print(lstart + llen, rstart + rlen - 1)
    S = f1(S, lstart + llen, rstart + rlen - 1)
  else:
    #print(rstart + rlen, lstart + llen - 1)
    S = f1(S, rstart + rlen, lstart + llen - 1)
  #print(S)

print(f3(S))

Submission status: Time Limit Exceeded

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

cur = S[0]
n = 1
n_l = []
for s in S[1:]:
    if s == cur:
        n += 1
    else:
        n_l.append(n)
        n = 1
    cur = s
n_l.append(n)
#print(n_l)

for _ in range(K):
    if len(n_l) > 3:
        max1, max2 = sorted(n_l[1:-1], reverse=True)[:2]
        n_max1 = n_l[1:-1].index(max1) + 1
        n_l_ = n_l[:]
        n_l_[n_max1] = -1
        n_max2 = n_l_[1:-1].index(max2) + 1
        l, r = min(n_max1, n_max2), max(n_max1, n_max2)
        n_l = n_l[:l-1] + [n_l[l-1]+n_l[l]] + n_l[l+1:r] + [n_l[r]+n_l[r+1]] + n_l[r+2:]
        #print(n_l)
    else:
        n_l = [sum(n_l)]
print(sum(n_l)-len(n_l))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
def calc_h(S, N):
    h = 0
    for i in range(N):
        if S[i]=='L' and i!=0:
            if S[i]==S[i-1]:
                h+=1
        elif S[i]=='R' and i!=(N-1):
            if S[i]==S[i+1]:
                h+=1
    return(h)

revdic = {'L': 'R', 'R': 'L'}
hmax = calc_h(S, N)
Smax = S
for _ in range(K):
    if hmax==N:
        break

    hnum = []
    slist = []
    revdic = {'L': 'R', 'R': 'L'}
    for l in range(0, N):
        for r in range(0, N):
            if l<=r:
                _s = Smax[l:r][::-1]
                _s = ''.join([revdic[__s] for __s in _s])
                _S = Smax[:l] + _s + Smax[r:]
                # print(f'{S} -> {l},{r},{S[l:r]},{_s} -> {_S}')
                hnum.append(calc_h(_S, N))
                slist.append(_S)
    if max(hnum)>hmax:
        hmax = max(hnum)
        Smax= slist[hnum.index(max(hnum))]
             
#print(max(hnum), slist[hnum.index(max(hnum))])
print(hmax)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
s = input()
s = s.replace('LR', 'L,R')
s = s.replace('RL', 'R,L')
s = s.split(',')
s = list(map(len, s))
l = 2*k+1
ans = -1

if l >= len(s):
    ans = sum(s)-1
else:
    for i in range(len(s)-l+1):
        cnt = 0
        cnt += sum(list(np.array(s[:i])-1))
        cnt += sum(s[i:l+i])-1
        cnt += sum(list(np.array(s[l+i:])-1))
        ans = max(ans, cnt)   
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
for _ in range(k):
    lr_f = 0
    rl_f = 0
    temp = None
    target_point = [0, 0]
    pair_f = False
    for i, content in enumerate(s):
        if [temp, content] == ['L', 'R']:
            if rl_f and not rl_f == i-1:
                target_point = [rl_f, i-1]
                pair_f = True
                break
            elif not lr_f:
                lr_f = i
        if [temp, content] == ['R', 'L']:
            if lr_f and not lr_f == i-1:
                target_point = [lr_f, i-1]
                pair_f = True
                break
            elif not rl_f:
                rl_f = i
        temp = content
    if not pair_f:
        if lr_f and s[-1] == 'R':
            target_point = [lr_f, len(s)-1]
        elif rl_f and s[-1] == 'L':
            target_point = [rl_f, len(s)-1]
        else:
            break
    temp_s = s[:target_point[0]]
    for i in reversed(range(target_point[0], target_point[1]+1)):
        if s[i] == 'R':
            temp_s += 'L'
        elif s[i] == 'L':
            temp_s += 'R'
    temp_s += s[target_point[1]+1:]
    s = temp_s
temp = ''
point = 0
for content in s:
    if temp == content:
        point += 1
    temp = content
print(point)

Submission status: Time Limit Exceeded

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

def calc_n(SS):
  cnt=0
  if SS[0]=='R' and SS[1]=='R':
    cnt+=1
  for i in range(1,N-1):
    if SS[i]=='L' and SS[i-1]=='L':
      cnt+=1
    elif SS[i]=='R' and SS[i+1]=='R':
      cnt+=1
  if SS[-1]=='L' and SS[-2]=='L':
    cnt+=1  
  return cnt
  
new_queue=[S]
cnt=0

while(True):  
  cnt+=1
  queue=new_queue[:]

  for q in queue:
    for l in range(N):
      for r in range(l,N):
        new_S = q[0:l]
        for k in range(l,r+1):
          if q[r+l-k]=='L':
            new_S += 'R'
          else:
            new_S += 'L'
        new_S += q[r+1:N]
        new_queue.append(new_S)
        
  if cnt>=K:
    break
    
#print(new_queue)
answer=-1
answer_arg=""
for q in new_queue:
  if calc_n(q)>answer:
    answer=calc_n(q)
    answer_arg=q
    
print(answer)
#print(answer_arg)

Submission status: Time Limit Exceeded

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:
    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
        else:
            double+=1
        for sj in ll:
            if si == sj:
                i+=1
            else:
                i += 1
                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: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
s = []
cnt = 1
for i in range(N - 1):
    if S[i] == S[i + 1]:
        cnt += 1
        if i == N - 2:
            s.append([S[i], cnt])
    else:
        s.append([S[i], cnt])
        cnt = 1
        if i == N - 2:
            s.append([S[i + 1], cnt])
for i in range(1, min(len(s), 2*K), 2):
    if s[i][0] == "R":
        s[i][0] = "L"
    else:
        s[i][0] = "R"
T = ""
for i in range(len(s)):
    T += s[i][0] * s[i][1]
ans = 0
cnt = 0
for i in range(len(T) - 1):
    if T[i] == T[i + 1]:
        cnt += 1
        if i == len(T) - 2:
            ans += cnt
    else:
        ans += cnt
        cnt = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int,input().split())
s = [str(i) for i in input()]

LR = 0
RL = 0
tmp = 0
i,j = 0,0
for m in range(K):
	t_i,t_j = 0,0
	f = 0
	for k in range(N-1):
		si = s[k:k+2]
		if "".join(si) == "LR":
			LR = 1
			if RL == 0:
				i = k+1
			else:
				j = k
		if "".join(si) == "RL":
			RL = 1
			if LR == 0:
				i = k+1
			else:
				j = k
		if LR == 1 and LR == 1:
			if tmp == 0:
				t_i = i
				t_j = j
			elif i-j >= tmp:
				t_i = i
				t_j = j
			LR = 0
			RL = 0
	if t_j == 0:
		t_i = i
		t_j = N-1
	for l in range(t_i, t_j+1,1):
		if s[l] == "L":
			s[l] = "R"
		else:
			s[l] = "L"

c = 0
L = 0
R = 0
t = 0
for i in range(N):
	if s[i] == "L" and R == 1:
		if t>0:
			c += t-1
		t = 0
		R = 0
	if s[i] == "R" and L == 1:
		if t>0:
			c += t-1
		t = 0
		L = 0
	if s[i] == "L" and R == 0:
		t+=1
		L = 1
	if s[i] == "R" and L == 0:
		t += 1
		R = 1
	if i == N-1:
		if t>0:
			c+= t-1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
s = input()
s = s.replace('LR', 'L,R')
s = s.replace('RL', 'R,L')
s = s.split(',')
s = list(map(len, s))
l = 2*k+1
ans = -1

if l >= len(s):
    ans = sum(s)-1
else:
    for i in range(len(s)-l+1):
        cnt = 0
        cnt += sum(np.array(s[:i])-1)
        cnt += sum(s[i:l+i])-1
        cnt += sum(np.array(s[l+i:])-1)
        ans = max(ans, cnt)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
def calc_h(S, N):
    h = 0
    for i in range(N):
        if S[i]=='L' and i!=0:
            if S[i]==S[i-1]:
                h+=1
        elif S[i]=='R' and i!=(N-1):
            if S[i]==S[i+1]:
                h+=1
    return(h)

revdic = {'L': 'R', 'R': 'L'}
hmax = calc_h(S, N)
Smax = S
for _ in range(K):
    hnum = []
    slist = []
    revdic = {'L': 'R', 'R': 'L'}
    for l in range(0, N):
        for r in range(0, N):
            if l<=r:
                _s = Smax[l:r][::-1]
                _s = ''.join([revdic[__s] for __s in _s])
                _S = Smax[:l] + _s + Smax[r:]
                # print(f'{S} -> {l},{r},{S[l:r]},{_s} -> {_S}')
                hnum.append(calc_h(_S, N))
                slist.append(_S)
    if max(hnum)>hmax:
        hmax = max(hnum)
        Smax= slist[hnum.index(max(hnum))]
             
#print(max(hnum), slist[hnum.index(max(hnum))])
print(hmax)

Submission status: Time Limit Exceeded

Solution code:
# ABC140d
import sys
import re
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)
    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)
    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(sum(score)-len(score))

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N, K = map(int, input().split())
S = input()

counts = []
for k, v in groupby(S):
    counts.append(len(list(v)))
# print(counts)

counts_length = len(counts)

if K <= counts_length // 2:
    for i in range(K):
        if len(counts) == 2:
            counts = [counts[0] + counts[1]]
            break
        a, b, c = counts[0], counts[1], counts[2]
        max3 = sum((a, b, c))
        gattai = 0
        for index, d in enumerate(counts[3:]):
            a, b, c = b, c, d
            temp = sum((a, b, c))
            if temp > max3:
                max3 = temp
                gattai = index + 1
            # print(temp)
            # print(gattai)
        counts[gattai:gattai + 3] = [sum(counts[gattai:gattai + 3])]

    ans = 0
    for i in counts:
        ans += i - 1
    print(ans)
else:
    print(sum(counts)-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
s_ = np.array([1]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1

l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    a = s_[0]
    for i in s_[1:]:
        if i == a:
            ans += 1
        else:
            a = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bit_count(b, n):
    c = 0
    x = b & 1
    for _ in range(n-1):
        b >>= 1
        if x == (b & 1):
            c += 1
        x = b & 1
    return c

def bit_swap(b, l, r):
    x = ((2**(r-l+1)-1) << (l-1))
    return b ^ x

def bit_dump(b, n):
    s = ''
    for _ in range(n):
        s += ['L', 'R'][b & 1]
        b >>= 1
    return s

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

b = int(s.replace('L', '0').replace('R', '1'), 2)

result = 0
queue = [(0, b, bit_count(b, n))]
visited = set([b])
while queue:
    depth, b, bc = queue.pop()
    if k == depth:
        result = max(result, bc)
        continue
    if depth < k:
        for l in range(1, n+1):
            for r in range(l, n+1):
                nb = bit_swap(b, l, r)
                if nb not in visited:
                    visited.add(nb)
                    nbc = bit_count(nb, n)
                    if bc < nbc:
                        queue.append((depth+1, nb, nbc))
print(result)

Submission status: Time Limit Exceeded

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

cur = S[0]
n = 1
n_l = []
for s in S[1:]:
    if s == cur:
        n += 1
    else:
        n_l.append(n)
        n = 1
    cur = s
n_l.append(n)
#print(n_l)

for _ in range(K):
    if len(n_l) > 2:
        max1, max2 = sorted(n_l[1:-1], reverse=True)[:2]
        n_max1 = n_l[1:-1].index(max1) + 1
        n_max2 = len(n_l[1:-1]) - list(reversed(n_l[1:-1])).index(max2)
        l, r = min(n_max1, n_max2), max(n_max1, n_max2)
        if l == r:
            n_l = n_l[:l-1] + [n_l[l-1]+n_l[l]+n_l[l+1]] + n_l[r+2:]
        else:
            n_l = n_l[:l-1] + [n_l[l-1]+n_l[l]] + n_l[l+1:r] + [n_l[r]+n_l[r+1]] + n_l[r+2:]
        #print(n_l)
    elif len(n_l) == 2:
        n_l = [n_l[0]+n_l[1]]
print(sum(n_l)-len(n_l))

Submission status: Time Limit Exceeded

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

final_ans = 0
if len(ans[0]) == 2:
    print(n-1)
elif len(ans[0]) == 1:
    print(n-1)
else:
    for i in range(k):
  #      print(i)
        b = max(ans[i][1:len(ans[i])-1])
        ind = ans[i][1:len(ans[i])-1].index(b)+1
   #     print(ind,b)
        if ind == 0:
      #      ans = [ans[ind]+ans[ind+1]] + ans[2:]
            for j in [ans[i][ind]+ans[i][ind+1]] + ans[2:]:
                ans[i+1].append(j)

        elif ind == len(ans[i])-1:
      #      ans = ans[:len(ans)-2] + [ans[ind-1]+ans[ind]]
            for j in ans[i][:len(ans[i])-2] + [ans[i][ind-1]+ans[i][ind]]:
                ans[i+1].append(j)
        else:
      #      ans = ans[:ind-1] + [ans[ind-1]+ans[ind]+ans[ind+1]] + ans[ind+2:]
            for j in ans[i][:ind-1] + [ans[i][ind-1]+ans[i][ind]+ans[i][ind+1]] + ans[i][ind+2:]:
                ans[i+1].append(j)
  #      print(ans)
   # print(ans)

    for i in ans[-1]:
        final_ans += i-1
    print(final_ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
# n = 10 ** 5
# k = 20000
# s=""
# for i in range(n//4):
#     s += "LRRL" 
s_ = np.array([1]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1



l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    a = s_[0]
    for i in range(1,n):
        if s_[i] == a:
            ans += 1
        else:
            a = s_[i]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
# n = 10 ** 5
# k = 20000
# s=""
for i in range(n//4):
    s += "LRRL" 
s_ = np.array([1]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1



l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    a = s_[0]
    for i in range(1,n):
        if s_[i] == a:
            ans += 1
        else:
            a = s_[i]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,k = inpl()
s = input()
cntlr = []
tmp = ''
cnt = 0
for i in range(n):
    if i == 0:
        tmp = s[i]
        cnt = 1
    else:
        if tmp == s[i]:
            cnt += 1
        else:
            cntlr.append(cnt)
            tmp = s[i]
            cnt = 1
cntlr.append(cnt)
# print(cntlr)
nn = len(cntlr)
if nn == 1:
    print(n-1)
    quit()
if nn%2==0:
    for i in range(k):
        if len(cntlr) > 4:
            cntlr[0] += cntlr[len(cntlr)-3]
            cntlr[len(cntlr)-2] += cntlr[1]
            del(cntlr[len(cntlr)-3])
            del(cntlr[1])
            for k in range((len(cntlr)-3)//2):
                cntlr[k+1],cntlr[len(cntlr)-3-k]=cntlr[len(cntlr)-3-k],cntlr[k+1]
        elif len(cntlr) ==  4:
            cntlr[0] += cntlr[1] + cntlr[2]
            del(cntlr[1:3])
        else:
            print(n-1)
            quit()
else:
    for i in range(k):
        if len(cntlr) > 3:
            cntlr[0] += cntlr[len(cntlr)-2]
            cntlr[-1] += cntlr[1]
            del(cntlr[len(cntlr)-2])
            del(cntlr[1])
            for k in range((len(cntlr)-2)//2):
                cntlr[k+1],cntlr[-2] = cntlr[-2],cntlr[k+1]
        else:
            print(n-1)
            quit()
res = 0
for i in cntlr:
    if i >= 2:
        res += i-1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,K=map(int,input().split())
s=input()
ans=0
l1=deque([])
l2=deque([])
for i in range(N-1):
  if s[i:i+2]=='LR':
    l1.append(i)
  elif s[i:i+2]=='RL':
    l2.append(i)
  elif s[i]=='L' and s[i+1]=='L':
    ans+=1
  elif s[i]=='R' and s[i+1]=='R':
    ans+=1

while K>0 and len(s)-2>ans:
  if l1[0]<l2[-1]:
    n1=l1.popleft()
    n2=l2.pop()
    l1=deque([(n1+n2-n) for n in l1 if n<n2])
    l2=deque([(n1+n2-n) for n in l2])
    ans+=2
    K-=1
if len(s)-2<=ans and K>=1:
  ans=len(s)-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy
n,k = map(int, input().split())
s = list(input())

a=0
y=n
x=n

for i in range(k):
    maxm = 0
    maxs = copy.deepcopy(s)
    for l in range(n-1):
        for r in range(l+1,n):
            test = copy.deepcopy(s)
            for ang in range(l,r+1):
                if test[ang] == 'L':
                    test[ang] = 'R'
                else:
                    test[ang] = "L"
            torkn = 0
            for j in range(0,n):
                if j!=n-1:
                    if test[j] == test[j+1] and test[j] == 'R':
                        torkn += 1
                if j!=0 :
                    if test[j] == test[j-1] and test[j] == 'L':
                        torkn+=1
            if(maxm < torkn):
                y=l
                x=r
                maxm = torkn
                a = torkn
                maxs = copy.deepcopy(test)
    s = copy.deepcopy(maxs)

print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int,input().split()) 
s = input()
s_ = np.array([0]*n)
for i in range(n):
    if s[i] == 'L':
        s_[i] = -1 
    else:
        s_[i] = 1



l = 0
r = n-1
l_value = s_[l]
r_value = s_[r]
count = 0
while l < r and count < k:
    if s_[l] == l_value and s_[r] == r_value:
        l += 1
        r -= 1
    elif s_[l] != l_value and s_[r] == r_value:
        r -= 1
    elif s_[l] == l_value and s_[r] != r_value:
        l += 1
    else:
        s_[l:r+1] *= -1
        count += 1
        l += 1
        r -= 1

ans = 0
if count < k:
    ans = n - 1
else:
    a = s_[0]
    for i in range(1,n):
        if s_[i] == a:
            ans += 1
        else:
            a = s_[i]


print(ans)

Submission status: Time Limit Exceeded

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

final_ans = 0
if len(ans) == 2:
    print(n-1)
elif len(ans) == 1:
    print(n-1)
else:
    for i in range(k):
        ans2 = []
  #      print(i)
        b = max(ans[1:len(ans)-1])
        ind = ans[1:len(ans)-1].index(b)+1
   #     print(ind,b)
        if ind == 0:
      #      ans = [ans[ind]+ans[ind+1]] + ans[2:]
            for j in [ans[ind]+ans[ind+1]] + ans[2:]:
                ans2.append(j)
            ans = ans2
        elif ind == len(ans)-1:
      #      ans = ans[:len(ans)-2] + [ans[ind-1]+ans[ind]]
            for j in ans[:len(ans)-2] + [ans[ind-1]+ans[ind]]:
                ans2.append(j)
            ans = ans2
        else:
      #      ans = ans[:ind-1] + [ans[ind-1]+ans[ind]+ans[ind+1]] + ans[ind+2:]
            for j in ans[:ind-1] + [ans[ind-1]+ans[ind]+ans[ind+1]] + ans[ind+2:]:
                ans2.append(j)
            ans = ans2
  #      print(ans)
   # print(ans)

    for i in ans:
        final_ans += i-1
    print(final_ans)

Submission status: Time Limit Exceeded

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

largest = 0
largest_left_index = -1

sum_list = list()

count = 0
for i in range(N):
    if S[i] == "L":
        if count <= 0:
            count = count - 1
        else:
            sum_list.append(count)
            count = -1
    elif S[i] == "R":
        if count >= 0:
            count = count + 1
        else:
            sum_list.append(-count)
            count = 1
else:
    sum_list.append(count) if count > 0 else sum_list.append(-count)

for i in range(K):
    length = len(sum_list)
    current_max = 0
    current_max_index = 0
    for j in range(length):
        current_sum = sum_list[j]
        if j < length - 1:
            current_sum = current_sum + sum_list[j+1]
        if j < length - 2:
            current_sum = current_sum + sum_list[j+2]

        if current_sum > current_max:
            current_max = current_sum
            current_max_index = j

    if current_max_index < length - 2:
        sum_list.pop(current_max_index + 2)
    if current_max_index < length - 1:
        sum_list.pop(current_max_index + 1)
    sum_list.pop(current_max_index)
    sum_list.insert(current_max_index, current_max)

res = 0
for i in range(len(sum_list)):
    res = res + sum_list[i] - 1

print(res)

Submission status: Time Limit Exceeded

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

tmp = []
cnt = 1
s += '-'
for i in range(n):
    if s[i] == s[i + 1]:
        cnt += 1
    else:
        tmp.append(cnt)
        cnt = 1

for i in range(k):
    if len(tmp) == 1:
        break
    elif len(tmp) == 2:
        tmp = [tmp[0] + tmp[1]]
    else:
        tmp = [tmp[0] + tmp[1] + tmp[2]] + tmp[3:]
# print(tmp)

if len(tmp) == 1:
    print(tmp[0] - 1)
else:
    total = 0
    for j in tmp:
        if j > 1:
            total += j - 1
    print(total)

Submission status: Time Limit Exceeded

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

def solve():
    global K, S
    concat_S = S[:]
    while 'LL' in concat_S:
        concat_S = concat_S.replace('LL', 'L', 1)
    while 'RR' in concat_S:
        concat_S = concat_S.replace('RR', 'R', 1)

    ans = len(S) - len(concat_S)
    if len(concat_S) >= 4:
        # 2個ずつ消す
        num_rm = min(K, (len(concat_S)-2)//2)
        K -= num_rm
        ans += num_rm * 2
        len_concat_S = len(S) - ans

        if K:
            if len_concat_S == 3:
                ans += 2
            elif len_concat_S == 2:
                ans += 1
        print(ans)
        return
    if K:
        if len(concat_S) == 3:
            ans += 2
        elif len(concat_S) == 2:
            ans += 1
        
    print(ans)
    return

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def bit_count(b, n):
    c = 0
    x = b & 1
    for _ in range(n-1):
        b >>= 1
        if x == (b & 1):
            c += 1
        x = b & 1
    return c

def bit_swap(b, l, r):
    x = ((2**(r-l+1)-1) << (l-1))
    return b ^ x

def bit_dump(b, n):
    s = ''
    for _ in range(n):
        s += ['L', 'R'][b & 1]
        b >>= 1
    return s

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

b = int(s.replace('L', '0').replace('R', '1'), 2)

result = 0
queue = [(0, b)]
visited = set([b])
while queue:
    depth, b = queue.pop()
    if k == depth:
        result = max(result, bit_count(b, n))
        continue
    if depth < k:
        for l in range(1, n+2):
            for r in range(l, n+2):
                #print(bit_dump(bit_swap(b, l, r), n))
                nb = bit_swap(b, l, r)
                if nb not in visited:
                    visited.add(nb)
                    queue.append((depth+1, nb))
print(result)

Submission status: Time Limit Exceeded

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

n,k = [int(i) for i in readline().split()]
s = input()
d = {'L':-1,'R':1}
l = [d[i] for i in s]

ans = 0

for _ in range(k):
  left = 0
  flag_left = 0
  right = n-1
  flag_right = 0
  while left < right and not (flag_left and flag_right):
    if l[left] != l[left+1] and not flag_left:
      left += 1
      flag_left = 1
    elif l[left] == l[left+1] and not flag_left:
      left += 1
    if l[right] != l[right-1] and not flag_right:
      right -= 1
      flag_right = 1
    elif l[right] == l[right-1] and not flag_right:
      right -= 1
  if flag_left == 0:
    left = 0
  if flag_right == 0:
    right = n-1
  if flag_left == flag_right == 1 and left > right:
    left = 0
  for i in range(left, right+1):
    l[i] *= -1

for i in range(n-1):
  if l[i] == l[i+1]:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
S = [1 if x=='R' else -1 for x in input()]
r = 0
for i in range(K):
    l = r
    f = True
    prev = S[0]
    for j in range(l, N):
        current = S[j]
        if current != prev:
            l = j
            f = False
            break
        prev = current
    if f:
        break

    r = N - 1
    prev = S[l]
    for j in range(l+1, N):
        current = S[j]
        if current != prev:
            r = j - 1
            break
        prev = current
    left = S[:l]
    target = S[l:r+1]
    right = S[r+1:]
    target.reverse
    target = [-x for x in target]
    S = left + target + right

S.insert(0, 1)
S.append(-1)
ans = 0
for i in range(N):
    x = S[i+1]
    y = S[i+1+x]
    if x == y:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import re
n, k = [int(i) for i in sys.stdin.readline().split()]
s = input()
def _reverse(text):
    res = text[::-1]
    res = ["R" if i == "L" else "L" for i in res]
    res = "".join(res)
    return res
"""
for i in range(k):
    left = s.find("R")
    left = 0 if left == -1 else left
    right = s.rfind("R") + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
s = copy.deepcopy(s_origi)
"""
for i in range(k):
    left = s.find("LR") + 1
    left = 0 if left == -1 else left
    right = s.rfind("RL")
    right = n if right == -1 else right + 1

    s = s[:left] + _reverse(s[left:right]) + s[right:]
    #s = copy.deepcopy(s_new)
cnt = sum([len(i) - 1 for i in re.findall(r"R{2,}|L{2,}", s)])
print(cnt)

Submission status: Time Limit Exceeded

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

# K個の塊を逆向きにする
R = [0] + [i for i in range(1, len(S)) if S[i-1] != S[i]] + [N]

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

ans = 0
for i in range(len(R)):
  s = list(S)
  l = R[max(0, i-(2*K+1))]
  r = R[i]
  s = [s[l] if l <= i < r else c for i,c in enumerate(s)]
  #print(l,r,s,score(s))
  ans = max(ans, score(s))
print(ans)

Submission status: Time Limit Exceeded

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

# K個の塊を逆向きにする
R = [0] + [i for i in range(1, len(S)) if S[i-1] != S[i]] + [N]

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

ans = 0
for i in range(len(R)):
  s = list(S)
  l = R[max(0, i-(2*K+1))]
  r = R[i]
  s = [s[l] if l <= i < r else c for i,c in enumerate(s)]
  #print(l,r,s,score(s))
  ans = max(ans, score(s))
print(ans)