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:
def calculate_happiness(S: str, N: int) -> int:
  if N == 1:
    return 0
  happiness = 0
  if S[0] == S[1] == 'R':
    happiness += 1
  if S[-1] == S[-2] == 'L':
    happiness += 1
  for i in range(1, N-1):
    if S[i] == S[i+1] == 'R':
      happiness += 1
    elif S[i] == S[i-1] == 'L':
      happiness += 1
  return happiness
 
def change_string(S: str, l: int, r: int) -> str:
  part = S[l:r+1][::-1].replace('R', '_')
  part = part.replace('L', 'R').replace('_', 'L')
  return S[:l] + part + S[r+1:]
 
N, K = list(map(int, input().split()))
S = input()
happiness = calculate_happiness(S, N)
opt_S = S
opt_happiness = happiness
for k in range(K):
  S = opt_S
  for l in range(N-1):
    for r in range(l+1, N):
      new_S = change_string(S, l, r)
      happiness = calculate_happiness(new_S, N)
      if happiness > opt_happiness:
        opt_S = new_S
        opt_happiness = happiness
print(opt_happiness)

Submission status: Time Limit Exceeded

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

l=-1
r=-1
for i in range(K):
    l+=1
    for j in range(l,N-1):
        if S[j]!=S[j+1]:
            l=j
            break
    r+=1
    for k in range(r,N-1):
        if S[N-1-k]!=S[N-1-k-1]:
            r=k
            break
    if l+1>N-1-r-1:
        ans=N-1
        break

nomove=S[l+1:N-1-r]
same=0
for i in range(len(nomove)-1):
    if nomove[i+1]==nomove[i]:
        same+=1

if l+1>N-1-r-1:
    ans=N-1
else:
    ans=(l+1)+(r+1)+same

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
people = list(input())
groups = []
count = 1
for q in range(1, n):
    if people[q] == people[q - 1]:
        count += 1
    else:
        groups.append(count)
        count = 1
groups.append(count)
l = len(groups)
if k >= l // 2:
    print(n - 1)
else:
    t = 0
    for _ in range(k):
        l = len(groups)
        trio = []
        for q in range(l - 2):
            trio.append(groups[q] + groups[q + 1] + groups[q + 2])
        b = max(trio)
        a = trio.index(b)
        del groups[a]
        del groups[a]
        del groups[a]
        groups.insert(a, b)
        trio.clear()
    for q in groups:
        t += q - 1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=input()
li=[]
seq=1
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        seq+=1
    else:
        li.append(seq)
        seq=1
        
li.append(seq)


for i in range(k):
    if len(li)>=3:
        tmp=li[0]+li[1]+li[2]
        del li[0:3]
        li.insert(0,tmp)
    elif len(li)==2:
        tmp=li[0]+li[1]
        del li[0:2]
        li.insert(0,tmp)
    elif len(li)==1:
        break

print(sum(list(map(lambda x:x-1, li))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
str = list(input())
length = len(str)-1
a = list(str)
b = list(str)
max = -1
for i in range(k):
    for j in range(length):
        a[j] = str[j]

    for j in range(length):
        for m in range(j,length):
            a = list(str)
            for l in range(m-j+1):
                if str[j+l] == 'L':
                    a[m-l] = 'R'
                else:
                    a[m-l] = 'L'
            count = 0
            for l in range(length-1):
                if a[l] == a[l+1]:
                    count += 1
            if count > max:
                max = count
                for l in range(length):
                    b[l] = a[l]
    for j in range(length):
        str[j] = b[j]
print(max)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
str = list(input())
length = len(str)
a = list(str)
b = list(str)
max = -1
for i in range(k):
    for j in range(length):
        a[j] = str[j]

    for j in range(length):
        for m in range(j,length):
            a = list(str)
            for l in range(m-j+1):
                if str[j+l] == 'L':
                    a[m-l] = 'R'
                else:
                    a[m-l] = 'L'
            count = 0
            for l in range(length-1):
                if a[l] == a[l+1]:
                    count += 1
            if count > max:
                max = count
                for l in range(length):
                    b[l] = a[l]
    for j in range(length):
        str[j] = b[j]
print(max)

Submission status: Time Limit Exceeded

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])
s = tuple(str(input()))
 
c = 0
t = 0
ans = 0
 
for i in range(n-1):
  try:
    if s[i] == s[i+1]:
      t += 1
    #print(t)
  except IndexError:
    continue
  for j in range(1,n-1):
    #print(c)
    try:
      if s[i-1] != s[i] and s[i] == s[j] and s[i-1] == s[j+1]:
        c += 1
        if k <= c:
          break
        continue
    except IndexError:
      continue


if k <= c:
  ans = t + 2 * k
else:
  ans = t + 2 * c + (k - c)

if ans < n:
  print(ans)
else:
  print(n-1)

Submission status: Time Limit Exceeded

Solution code:
def change_lr(s, l, r):
    s2 = list(s)
    for i in range(r-l+1):
        if s[l+i] == 'L':
            s2[r-i] = 'R'
        else:
            s2[r-i] = 'L'
    return s2
  
n, k = map(int, input().split())
s = list(input())
ans = 0

for j in range(k):
    c1 = ''
    c2 = ''
    start = 0
    end = 0
    for i in range(1,n):
        if s[i] != s[i-1]:
            c1 = s[i] 
            c2 = s[i-1] 
            start = i
            for k in range(i+2,n):
                if s[k-1] == c1 and s[k] == c2:
                    end = k-1
                    break
            else:
                continue
            break
    if end == 0:
        end = start
        end = n-1

    s = change_lr(s, start, end)

for i in range(1, len(s)):
    if s[i-1] == s[i]:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

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

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

for _ in range(k):
    if len(tmp)==1:
        break
    elif len(tmp)==2:
        tmp=[tmp[0]+tmp[1]]
        continue
    tmp=[tmp[0]+tmp[1]+tmp[2]]+tmp[3:]

ans=sum(tmp)-len(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

def searchRL(S):
    ans = []
    for i in range(N-1):
        if S[i] == "R" and S[i+1] == "L":
            ans.append(i)
    return ans

def searchLR(S):
    ans = []
    for i in range(N-1):
        if S[i] == "L" and S[i+1] == "R":
            ans.append(i)
    return ans

def reverse(S):
    S = list(S)
    for i in range(len(S)):
        if S[i] == 'L':
            S[i] = 'R'
        if S[i] == 'R':
            S[i] = 'L'
    return ''.join(S)


def solve(S):
    if len(RL) == 0 and len(LR) == 0:
        return S, 0
    if len(RL) == 0:
        S = reverse(S[LR[0]::-1]) + S[LR[0]+1:]
        LR.pop(0)
        return S, 1
    if len(LR) == 0:
        S = reverse(S[RL[0]::-1]) + S[RL[0]+1:]
        RL.pop(0)
        return S, 1
    fir = min(LR[0], RL[0])
    sec = max(LR[0], RL[0])
    S = S[:fir+1] + reverse(S[sec:fir:-1]) + S[sec+1:]
    LR.pop(0)
    RL.pop(0)
    return S, 2

def cal(S):
    ans = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            ans +=1
    return ans

RL = searchRL(S)
LR = searchLR(S)
ans = cal(S)
for i in range(K):
    S, res = solve(S)
    ans += res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

def searchRL(S):
    ans = []
    for i in range(N-1):
        if S[i] == "R" and S[i+1] == "L":
            ans.append(i)
    return ans

def searchLR(S):
    ans = []
    for i in range(N-2,-1,-1):
        if S[i] == "L" and S[i+1] == "R":
            ans.append(i)
    return ans

def reverse(S):
    S = list(S)
    for i in range(len(S)):
        if S[i] == 'L':
            S[i] = 'R'
        if S[i] == 'R':
            S[i] = 'L'
    return ''.join(S)


def solve(S):
    RL = searchRL(S)
    LR = searchLR(S)
    if len(RL) == 0 and len(LR) == 0:
        return S, 0
    if len(RL) == 0:
        S = reverse(S[LR[0]::-1]) + S[LR[0]+1:]
        return S, 1
    if len(LR) == 0:
        S = reverse(S[RL[0]::-1]) + S[RL[0]+1:]
        return S, 1
    fir = min(LR[0], RL[0])
    sec = max(LR[0], RL[0])
    S = S[:fir+1] + reverse(S[sec:fir:-1]) + S[sec+1:]
    return S, 2

def cal(S):
    ans = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            ans +=1
    return ans


ans = cal(S)
for i in range(K):
    S, res = solve(S)
    ans += res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
L = 'L'
R = 'R'
hp = []
K = 0
def happiness(s):
    re = 0
    if len(s) == 1:
        return 0
    
    if s[0] == R and s[1] == R:
        re += 1

    for i in range(1,len(s)-1):
        if s[i] == L and s[i-1] == L:
            re += 1
        if s[i] == R and s[i+1] == R:
            re += 1

    if s[-2] == L and s[-1] == L:
        re += 1
    return re


def change(s, l, r):
    temp1 = s[l:r+1]
    #print(temp1)
    temp2 = []
    #文字を入れ替え
    for t in temp1:
        if t == L:
            temp2.append(R)
        else:
            temp2.append(L)

    #順番を入れ替え
    re = s[0:l] + temp2[::-1] + s[r+1:]
##    print('    change l:{} r:{} s: {} -> {}'.
##          format(l, r, ''.join(s), ''.join(re)))
    return re


def repeat_change(k, s, N):
    global K
##    print('k:{}'.format(k))
    for i in range(K)[k:K]:
        #repeat_change(k-1, s, N)
        for l in range(N):
            for r in range(l, N):
                hp_s = happiness(s)
                temp_s = change(s, l, r)
                hp_temp_s = happiness(temp_s)
                hp.append(hp_temp_s)
##                print('i:{} l:{} r:{} s: {},{} -> {},{}'.
##                      format(i, l, r, ''.join(s), hp_s,
##                             ''.join(temp_s), hp_temp_s))
                if i+1 < K and hp_s < hp_temp_s:
                    repeat_change(i+1, temp_s, N)

            
if __name__ == '__main__':
    N, K = map(int, input().split())
    S = list(input())
    repeat_change(0, S, N)
    print(max(hp))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
S = list(input())

_l = 0
for _k in range(k):
    l = _l
    r = len(S) - 1
    for i in range(l + 1, len(S) - 1):
        if l == _l and S[i] != S[i - 1]:
            l = i
        if l > _l and S[i] == S[l] and S[i + 1] != S[l]:
            r = i
            break

    buf = S[:]
    for i in range(r - l + 1):
        S[r - i] = 'L' if buf[l + i] == 'R' else 'R'

    if _k > n / 2:
        break

    _l = l

score = 0
for i in range(len(S)):
    if i > 0 and S[i] == 'L' and S[i - 1] == 'L':
        score += 1
    elif i < len(S) - 1 and S[i] == 'R' and S[i + 1] == 'R':
        score += 1

print(score)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
S = list(input())

for _k in range(k):
    l = 0
    r = len(S) - 1
    for i in range(1, len(S) - 1):
        if l == 0 and S[i] != S[i - 1]:
            l = i
        if l > 0 and S[i] == S[l] and S[i + 1] != S[l]:
            r = i
            break

    buf = S[:]
    for i in range(r - l + 1):
        S[r - i] = 'L' if buf[l + i] == 'R' else 'R'

    if _k > n / 2:
        break

score = 0
for i in range(len(S)):
    if i > 0 and S[i] == 'L' and S[i - 1] == 'L':
        score += 1
    elif i < len(S) - 1 and S[i] == 'R' and S[i + 1] == 'R':
        score += 1

print(score)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
S = list(input())

for _ in range(k):
    l = 0
    r = len(S) - 1
    for i in range(1, len(S) - 1):
        if l == 0 and S[i] != S[i - 1]:
            l = i
        if l > 0 and S[i] == S[l] and S[i + 1] != S[l]:
            r = i
            break

    buf = S[:]
    for i in range(r - l + 1):
        S[r - i] = 'L' if buf[l + i] == 'R' else 'R'

score = 0
for i in range(len(S)):
    if i > 0 and S[i] == 'L' and S[i - 1] == 'L':
        score += 1
    elif i < len(S) - 1 and S[i] == 'R' and S[i + 1] == 'R':
        score += 1

print(score)

Submission status: Time Limit Exceeded

Solution code:
def new_list(s_list):
    s_list_new = [s_list[0]]
    for i, s in enumerate(s_list):
        if i >= 1:
            if s != s_list[i - 1]:
                s_list_new.append(s)
    return s_list_new

if __name__ == "__main__":
 
    n, k = map(int, input().split())
    stext = str(input())
    s_list = [s for s in stext]
    s_list = new_list(s_list)
    cnt_l = s_list.count('L')
    cnt_r = s_list.count('R')
    replace = 'L'
    replaced = 'R'
    if cnt_l > cnt_r: replace = 'R'
    if cnt_l > cnt_r: replaced = 'L'
    if cnt_l == cnt_r:
        if s_list[0] == 'L': 
            replace = 'R'
            replaced = 'L'
    
    for i in range(k):
        for j, s in enumerate(s_list):
            if s == replace:
                s_list[j] = replaced
                break
    
    s_list = new_list(s_list)
    print('{0}'.format(n - len(s_list)))

Submission status: Time Limit Exceeded

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

tmp_leng = 1
tmp_hito = S[0]
for i in range(1,N):
    if S[i] == tmp_hito:
        tmp_leng += 1
    else:
        bubun.append(tmp_leng)
        tmp_leng = 1
    tmp_hito = S[i]
bubun.append(tmp_leng)

for i in range(K):
    if len(bubun) < 3:
        bubun = [sum(bubun)]
        break
    tmp = []
    for j in range(len(bubun)-2):
        tmp.append(bubun[j] + bubun[j+1] + bubun[j+2])
    
    j = 0
    matome = tmp.index(max(tmp))
    new_bubun = []
    while j < len(bubun):
        if j == matome:
            new_bubun.append(max(tmp))
            j += 3
        else:
            new_bubun.append(bubun[j])
            j += 1
    bubun = new_bubun

ans = 0
for _ in bubun:
    ans += _-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def turn(S,l,r):
    S1=S[:l]
    S2=S[l:r+1][::-1]
    S3=S[r+1:]
    S2=S2.replace('L',' ')
    S2=S2.replace('R','L')
    S2=S2.replace(' ','R')
    return S1+S2+S3

def score(S):
    ans=0
    for i in range(N):
        if((i<N-1 and S[i]==S[i+1]=='R') or (i>0 and S[i]==S[i-1]=='L')):
            ans+=1
    return ans

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

for i in range(K):
    l=r=-1
    for j in range(1,N-1):
        if S[j]!=S[0]:
            l=j
            break
    for k in range(l+1,N-1):
        if S[k]==S[0]:
            r=k-1
            break
    if l==r==-1:
        break
    elif r==-1:
        S=turn(S,l,N-1)
    else:
        S=turn(S,l,r)

print(score(S))

Submission status: Time Limit Exceeded

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

def split(s):
    new = [s[0]]
    for i in range(n-1):
        if s[i] != s[i+1]:
            new.append(s[i+1])
        else:
            new[-1] += s[i+1]
    return new

def transform(s, k):
    for _ in range(k):
        s = split(s)
        if len(s) == 1:
            s = ''.join(s)
            break
        idx = 1
        s[idx] = s[idx].replace('L', 'X').replace('R', 'L').replace('X', 'R')
        s = ''.join(s)
    return s


s = transform(s, k)


def count(s):
    cnt = 0
    for i in range(n):
        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: Time Limit Exceeded

Solution code:
def kaiten(parts):
    parts = reversed(parts)
    parts = ''.join(parts)
    parts = parts.replace('L', 'Z')
    parts = parts.replace('R', 'L')
    parts = parts.replace('Z', 'R')
    return list(parts)

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count += 1
        else:
            return count

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

for _ in range(k):
    l = s.find('LR')
    r = s.find('RL', l)
    l2 = s.find('RL')
    r2 = s.find('LR', l2)
    if l == r == l2 == r2 == -1:
        break
    _s = list(s)
    if 0 <= l and l < r:
        p = _s[l+1:r+1]
        _s[l+1:r+1] = kaiten(p)
    elif 0 <= l2 and l2 < r2:
        p = _s[l2+1:r2+1]
        _s[l2+1:r2+1] = kaiten(p)
    elif 0 <= l:
        p = _s[l+1:]
        _s[l+1:] = kaiten(p)
    elif 0 <= r:
        p = _s[:r+1]
        _s[:r+1] = kaiten(p)
    elif 0 <= l2:
        p = _s[l2+1:]
        _s[l2+1:] = kaiten(p)
    elif 0 <= r2:
        p = _s[:r2+1]
        _s[:r2+1] = kaiten(p)
    s = ''.join(_s)

score = occurrences(s, 'LL') + occurrences(s, 'RR')
print(score)

Submission status: Time Limit Exceeded

Solution code:
def kaiten(parts):
    parts = reversed(parts)
    parts = ''.join(parts)
    parts = parts.replace('L', 'Z')
    parts = parts.replace('R', 'L')
    parts = parts.replace('Z', 'R')
    return list(parts)

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count += 1
        else:
            return count

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

for _ in range(k):
    l = s.find('LR')
    r = s.find('RL', l)
    l2 = s.find('RL')
    r2 = s.find('LR', l2)
    _s = list(s)
    if 0 <= l and l < r:
        p = _s[l+1:r+1]
        _s[l+1:r+1] = kaiten(p)
    elif 0 <= l2 and l2 < r2:
        p = _s[l2+1:r2+1]
        _s[l2+1:r2+1] = kaiten(p)
    elif 0 <= l:
        p = _s[l+1:]
        _s[l+1:] = kaiten(p)
    elif 0 <= r:
        p = _s[:r+1]
        _s[:r+1] = kaiten(p)
    elif 0 <= l2:
        p = _s[l2+1:]
        _s[l2+1:] = kaiten(p)
    elif 0 <= r2:
        p = _s[:r2+1]
        _s[:r2+1] = kaiten(p)
    s = ''.join(_s)

score = occurrences(s, 'LL') + occurrences(s, 'RR')
print(score)

Submission status: Time Limit Exceeded

Solution code:
def kaiten(parts):
    _parts = []
    for i in range(len(parts)):
        _parts.append('L' if parts[-1-i] == 'R' else 'R')
    return _parts

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count += 1
        else:
            return count

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

for _ in range(k):
    l = s.find('LR')
    r = s.find('RL', l)
    l2 = s.find('RL')
    r2 = s.find('LR', l2)
    _s = list(s)
    if 0 <= l and l < r:
        p = _s[l+1:r+1]
        _s[l+1:r+1] = kaiten(p)
    elif 0 <= l2 and l2 < r2:
        p = _s[l2+1:r2+1]
        _s[l2+1:r2+1] = kaiten(p)
    elif 0 <= l:
        p = _s[l+1:]
        _s[l+1:] = kaiten(p)
    elif 0 <= r:
        p = _s[:r+1]
        _s[:r+1] = kaiten(p)
    elif 0 <= l2:
        p = _s[l2+1:]
        _s[l2+1:] = kaiten(p)
    elif 0 <= r2:
        p = _s[:r2+1]
        _s[:r2+1] = kaiten(p)
    s = ''.join(_s)

score = occurrences(s, 'LL') + occurrences(s, 'RR')
print(score)

Submission status: Time Limit Exceeded

Solution code:
def swap_list(S, l, r):
  result = list(S)
  count = r - l + 1
  for i in range(0, count):
    if S[r-i] == "R":
      result[l+i] = "L"
    elif S[r-i] == "L":
      result[l+i] = "R"
    
  return result 

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

for i in range(0, K):
  l_RL_index = -1
  l_LR_index = -1
  r_RL_index = N-1
  r_LR_index = N-1
  for j in range(0, N-1):  
    if S[j] == "R" and S[j+1] == "L":
      if l_LR_index != -1 and l_LR_index < j:
        r_RL_index = j
        break
      elif l_RL_index == -1:
        l_RL_index = j + 1
        j = j + 1 
    elif S[j] == "L" and S[j+1] == "R":
      if l_RL_index != -1 and l_RL_index < j:
        r_LR_index = j
        break
      elif l_LR_index == -1:
        l_LR_index = j + 1
        j = j + 1
  if r_RL_index < r_LR_index:
    S = swap_list(S, l_LR_index, r_RL_index)
  elif r_LR_index < r_RL_index:
    S = swap_list(S, l_RL_index, r_LR_index)
  else:
    if l_RL_index != -1:
      #print ("S = {0}, l_RL = {1}, r_LR = {2}".format(S, l_RL_index, r_LR_index))
      S = swap_list(S, l_RL_index, r_LR_index)
      #print("S_swap = {0}".format(S))
    elif l_LR_index != -1:
      #print ("S = {0}, l_LR = {1}, r_RL = {2}".format(S, l_LR_index, r_RL_index))
      S = swap_list(S, l_LR_index, r_RL_index)
      #print("S_swap = {0}".format(S))
  
  
result = 0
for i in range(0, N):
  if i == 0:
    if S[i] == "R" and S[i+1] == "R":
      result += 1
  elif i == N-1:
    if S[i] == "L" and S[i-1] == "L":
      result += 1
  else:
    if (S[i] == "R" and S[i+1] == "R") or (S[i] == "L" and S[i-1] == "L"):
      result += 1

print(result)

Submission status: Time Limit Exceeded

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

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
    
for i in range(K):
  ch_list=ch_list[2:]
  
#print(ch_list)
print(N-1-len(ch_list))

Submission status: Time Limit Exceeded

Solution code:
fd = {'L': 'R', 'R': 'L'}
def flip(s, l, r):
  def _flip(ss):
    return ''.join(fd[c] for c in ss)
  return _flip(s[l:r]) + s[:l] + s[r:]

def calc_score(n, s):
  score = 0
  for i in range(n):
    if i == 0:
      if s[i] == 'R' and s[i+1] == 'R':
        score += 1
      continue
    if i == len(s)-1:
      if s[i] == 'L' and s[i-1] == 'L':
        score += 1
      continue
    if s[i] == 'L' and s[i-1] == 'L':
      score += 1
    elif s[i] == 'R' and s[i+1] == 'R':
      score += 1
  return score

def summarize(n, s):
  r = []
  for i in range(n):
    if i == 0:
      c = s[i]
      start = i
      continue
    if c == s[i]:
      continue
    r.append((start, i))
    c = s[i]
    start = i
  r.append((start, i + 1))
  return r

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

from queue import PriorityQueue
q = PriorityQueue()
q.put((0, s))
scores = []
while not q.empty():
  p, s = q.get()
  if p == k:
    scores.append(calc_score(n, s))
    continue
  ll = summarize(n, s)
  if len(ll) == 1:
    scores.append(calc_score(n, s))
    break
  for l, r in ll:
  	q.put((p + 1, flip(s, l, r)))

print(max(scores))

Submission status: Time Limit Exceeded

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

ini = s[0]
ret += ini

is_renzoku = False

for key, v in enumerate(s):
    if key == 0:
        continue
    if v != ini and k != 0:
        is_renzoku = True
        if v == "R":
            ret += "L"
        else:
            ret += "R"
    else:
        if is_renzoku:
            k -= 1
        is_renzoku = False
        ret += v

ans = 0
for key, v in enumerate(ret):
    if key == 0: continue
    if v == ret[key-1]: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
Rs = []
now = S[0]
count = -1

for i in range(N):
    if S[i] == now:
        count += 1
    else:
        Rs.append(count)
        count = 0
        now = S[i]
Rs.append(count)
for _ in range(K):
    if len(Rs) > 3:
        add = [Rs[0] + Rs[1] + Rs[2] + 2]
        add.extend(Rs[3:])
        Rs = add
    elif len(Rs) == 3:
        Rs = [Rs[0] + Rs[1] + Rs[2] + 2]
        break
    elif len(Rs) == 2:
        Rs = [Rs[0] + Rs[1] + 1]
        break
    else:
        break
print(sum(Rs))

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    N, K = MAP()
    S = INPUT()

    for _ in range(K):
        left = N - 1
        right = 0
        l_flag = False
        r_flag = False
        for i in range(N):
            if S[i:i+2] == 'LR' and i < left:
                left = i + 1
                l_flag = True
            elif S[i:i+2] == 'RL' and i > right:
                right = i
                r_flag = True

        if not l_flag: left = 0
        if not r_flag: right = N - 1

        s_change = ""
        for i in reversed(range(right-left+1)):
            if S[left+i] == 'L': s_change += 'R'
            else: s_change += 'L'

        S = S[0:left] + s_change + S[right+1:N]

    ans = 0
    for i in range(N):
        if i == 0 and S[i] == 'L': continue
        elif i == N-1 and S[i] == 'R': continue
        else:
            if S[i-1:i+1] == 'LL': ans += 1
            elif S[i:i+2] == 'RR': ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

i = 0
ds = []
des = []
while i < k:
    ds = s[:]
    h = count_h(s)
    for l in range(n):
        for r in range(l,n-1):
            ds = ds[:l] + ds[l:r+1].translate(str.maketrans({"L":"R", "R":"L"})) + ds[r+1:]
            if h < count_h(ds):
                h = count_h(ds)
                des = ds[:]
            if h == n-1:
                break
            ds = s[:]
    i += 1
    s = des[:]

print(h)

Submission status: Time Limit Exceeded

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)
    elif len(A)==2:
        K+=1
        break
    else: break

if len(A)>=2 and K==0:
    print(sum(A)-len(A))
else:
    print(N-1)

Submission status: Time Limit Exceeded

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

num = 1
a = []

for i in range(1, n):
    if s[i] == s[i - 1]:
        num += 1
        continue
    elif s[i] != s[i - 1]: 
        a.append(num)
        num = 1

a.append(num)

m = len(a)
temp = 0

for x in range(m):
    while x <= k * 2:
        temp += a[x]
        
if m > k * 2:
    for j in range(k * 2 + 1, m):
        temp += a[j] -1

print(temp - 1)

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 si[0] == "L" and si[1] == "R":
			LR = 1
			if RL == 0:
				i = k+1
			else:
				j = k
		if si[0] == "R" and si[1] == "L":
			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:
def is_happy(i):
  if s[i]:
    if i == 0:
      return False
    else:
      return s[i-1]
  if not s[i]:
    if i == (n - 1):
      return False
    else:
      return not s[i+1]

def is_reverse(i, j):
  return (s[i] and not s[j]) or (not s[i] and s[j])

n, k = map(int, input().split())
_s = input()
s = []
s = [i == 'L' for i in _s]
for _ in range(k):
  d = []
  for l in range(n):
    for r in range(l+1, n):
      if l == 0 and r == n-1:
        continue
      if not is_happy(l) or not is_happy(r):
        c = 0
        if not is_happy(l):
          c += 1
        if not is_happy(r):
          c += 1
        d.append((l, r, c))
  max_a = 0
  d2 = []
  for i in range(len(d)):
    l, r, c = d[i]
    a = 0
    if r != n - 1:
      if is_reverse(l, r+1):
        a += 1
    if l != 0:
      if is_reverse(l-1, r):
        a += 1
    if a != 0:
      max_a = max(max_a, a)
      d2.append((l, r, c, a))
  for l, r, c, a in d2:
    if a == max_a:
      for i in range(l, r+1):
          s[i] = not s[i]
      tmp = s[l:r+1]
      tmp.reverse()
      s[l:r+1] = tmp
      break
c = 0
for i in range(n):
  if i == 0 and s[i]:
    continue
  if (i == n-1) and not s[i]:
    continue
  if s[i] and s[i-1]:
    c += 1
  elif not s[i] and not s[i+1]:
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
# LR と RL，RL と LRのペアを見つけてひっくり返す
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)