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: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
from collections import *
from bisect import *
from copy import deepcopy
mod = 10**9+7

N, K = map(int, input().split())
T = [0 if x == 'L' else 1 for x in input()]
f = 0
cnt = 0
for i in range(N-1):
    if T[i] != T[i+1]:
        cnt += 1
if cnt < 2:
    f = 1
S = deepcopy(T)
l, r, k = 0, N-1, 0
while l < N and S[l] == 1:
    l += 1
while l < N-1 and S[l+1] == 0:
    l += 1
while 0 <= r and S[r] == 1:
    r -= 1
while 0 < r and S[r-1] == 0:
    r -= 1
while l < r and k < K:
    k += 1
    for i in range(l+1, r):
        S[i] ^= 1
    while l < r and S[l] == S[l+1]:
        l += 1
    while l < r and S[r-1] == S[r]:
        r -= 1
ans1 = 0
i = 0
while i < N-1:
    c = 0
    while i < N-1:
        if S[i] == S[i+1]:
            i += 1
            c += 1
        else:
            ans1 += c
            c = 0
            i += 1
ans1 += c

S = deepcopy(T)
l, r, k = 0, N-1, 0
while l < N and S[l] == 0:
    l += 1
while l < N-1 and S[l+1] == 1:
    l += 1
while 0 <= r and S[r] == 0:
    r -= 1
while 0 < r and S[r-1] == 1:
    r -= 1
while l < r and k < K:
    k += 1
    for i in range(l+1, r):
        S[i] ^= 1
    while l < r and S[l] == S[l+1]:
        l += 1
    while l < r and S[r-1] == S[r]:
        r -= 1
ans2 = 0
i = 0
while i < N-1:
    c = 0
    while i < N-1:
        if S[i] == S[i+1]:
            i += 1
            c += 1
        else:
            ans2 += c
            c = 0
            i += 1
ans2 += c
print(max(ans1, ans2, f*N-1))

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n, k = na()
s = input()
ct = 0
lll = 1
li = []
for i in range(n-1):
    if s[i] == s[i+1]:
        ct += 1
        lll += 1
    else:
        li.append(lll)
        lll = 1
li.append(lll)
ans = []
"""
print(ct)
print(li[0::2])
print(li[1::2])
"""
for a, b in zip(li[0::2], li[1::2]):
    ans.append(a+b)
ans.sort()
if len(ans) == 1:
    print(ans[0] - 1)
else:
    for i in range(k):
        ct += (ans[-k] - 1)
    print(ct)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
s=input()
A=[]
p=s[0]
cnt=1
for i in range(1,len(s)):
	if p==s[i]:
		cnt+=1
	else:
		A.append(cnt)
		cnt=1
		p=s[i]
	
	if i==(N-1):
		A.append(cnt)


l=A.index(max(A))
r=l+1
LL=len(A)

for i in range(K):
	ll=0
	lf=0
	if l-2>=0:
		lf=2
		ll=A[l-2]+l[l-1]
	elif l-1>=0:
		lf=1
		ll=A[l-1]
	
	rr=0
	rf=0
	if r+2<=LL:
		rf=2
		rr=A[r]+A[r+1]
	elif r+1<=LL:
		rf=1
		rr=A[r]
	
	if ll>rr:
		l-=lf
	else:
		r+=rf

ans=0
for i in range(l):
	ans+=A[i]-1

for j in range(r,LL):
	ans+=A[j]-1

ans+=sum(A[l:r])-1
print(ans)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(n**3)
    return

#B
def B():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    ans = sum(b)
    for i in range(n-1):
        x = a[i]
        y = a[i+1]
        if y == x+1:
            ans += c[x-1]
    print(ans)
    return

#C
def C():
    n = I()
    b = LI()
    b.append(float("inf"))
    a = [min(b[i],b[i-1]) for i in range(n)]
    print(sum(a))
    return

#D
def D():
    n,k = LI()
    a = S()
    if a.count("L") in [0,n]:
        print(n-1)
        return
    if n == 1:
        print(0)
        return
    if n == 2:
        print(1)
        return
    ans = 0
    f = [0]*n
    for i in range(n-1):
        if a[i] == a[i+1]:
            ans += 1
            if a[i] == "L":
                f[i+1] = 1
            else:
                f[i] = 1
    f.append(0)
    f.append(0)
    r = n-1
    l = 0
    m = 0
    for i in range(k):
        if not i%2:
            while a[r] != "R":
                r -= 1
            while a[l] != "R":
                l += 1
        else:
            while a[r] != "L":
                r -= 1
            while a[l] != "L":
                l += 1
        if r <= l:
            print(n-1)
            return
        else:
            m += 2-f[l-1]-f[r+1]
    r = n-1
    l = 0
    m_ = 0
    for i in range(k):
        if i%2:
            while a[r] != "R":
                r -= 1
            while a[l] != "R":
                l += 1
        else:
            while a[r] != "L":
                r -= 1
            while a[l] != "L":
                l += 1
        if r <= l:
            print(n-1)
            return
        else:
            m_ += 2-f[l-1]-f[r+1]
    print(ans+max(m,m_))
    return

#E
def E():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    p = LI()
    r = [0]*n
    bit = [0]*(n+1)
    for i in range(n)[::-1]:
        r[i] = (n-i-1)-sum(p[i])
        add(p[i])
    print(r)
    l = [0]*n
    bit = [0]*(n+1)
    for i in range(n):
        l[i] = i-sum(p[i])
        add(p[i])
    print(l)

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
s=input()
A=[]
p=s[0]
cnt=1
for i in range(1,len(s)):
	if p==s[i]:
		cnt+=1
	else:
		A.append(cnt)
		cnt=1
		p=s[i]
	
	if i==(N-1):
		A.append(cnt)


l=A.index(max(A))
r=l+1
LL=len(A)

for i in range(K):
	ll=0
	lf=0
	if l-2>=0:
		lf=2
		ll=A[l-2]+l[l-1]
	elif l-1>=0:
		lf=1
		ll=A[l-1]
	
	rr=0
	rf=0
	if r+2<=LL:
		rf=2
		rr=A[r]+A[r+1]
	elif r+1<=LL:
		rf=1
		rr=A[r]
	
	if ll>rr:
		l-=lf
	else:
		r+=rf

ans=0
for i in range(l):
	ans+=A[i]-1

for j in range(r,LL):
	ans+=A[j]-1

ans+=sum(A[l:r])-1
print(ans)

Submission status: Runtime Error

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

l = []
for i in range(N):
  if i == 0:
    tmp = i
  if S[i - 1] != S[i]:
    l.append([tmp, i - 1, i - tmp])
    tmp = i
  if i == N - 1:
    l.append([tmp, i, i - tmp + 1])
l.sort(key = lambda x:x[2], reverse = True)

for k in range(K):
  if S[l[k][0]] == "L":
    S[l[k][0] : l[k][1] + 1] = "R" * l[k][2]
  else:
    S[l[k][0] : l[k][1] + 1] = "L" * l[k][2]

ans = 0
for i in range(N):
  if S[i] == "L":
    if i != 0 and S[i - 1] == "L":
      ans += 1
  else:
    if i != N - 1 and S[i + 1] == "R":
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
cnt = 1
li = []
li2 = []
ind_R = []
ind_L = []
for i in range(n-1):
    if s[i] == s[i+1] and s[i] == "R":
        cnt += 1
    elif s[i] == s[i+1] and s[i] == "L":
        cnt += 1
    else:
        li.append((s[i], cnt))
        cnt = 1
li.append((s[i], cnt))
cut = len(li) - 1

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

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
l=list(input())
s=l[0]
m=0
c=0
for i in range(1,n):
  if l[i]!=s:
    c+=1
    s=l[i]
if (c%2==0 and c//2<=k):
  print(n-1)
if (c%2==1 and c//2<k):
  print(n-1)
else:
  for i in range(1,n-1):
    if l[i]=="R" and l[i-1]=="R":
      m+=1   
    elif l[i]=="R" and l[i-1]=="L":
      pass
    elif l[i]=="L" and l[i-1]=="R":
      pass
    else:
      m+=1
  if l[-1]==l[-2] and l[-2]=="R":
    m+=1
  elif l[-1]==l[-2] and l[-2]=="L":
    m+=1
  print(m+k*2)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
import numpy as np
S = np.array(list(input()))
count = 0
if S[0] == 'R' and S[1] == 'R':
    count += 1
if S[-1] == 'L' and S[-2] == 'L':
    count += 1
for i in range(1, N-1):
    if S[i] == 'R' and S[i+1] == 'R':
        count += 1
    if S[i] == 'L' and S[i-1] == 'L':
        count += 1
count += K * 2
print(min(count, N-1))

Submission status: Runtime Error

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
if happy <= len(S) - 1:
  print(happy)
else:
  print(len(S) - 1)

Submission status: Runtime Error

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()

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

if k > 0 and now != s[n-1]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N,K = int(input())
p = list(map(int, input().split(" ")))
cnt = 0
for i in range(N):
  if p[i]=="l" and i!=0:
    if p[i]==p[i-1]:
      cnt += 1
  elif p[i]=="r" and i!=N-1:
    if p[i]==p[i+1]:
      cnt += 1
cnt += 2*K
if cnt>=N:
  cnt = N-1
print(cnt)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = 'R' + input() + 'L'
UH = [0] * (N + 1)
d = 'R'
for i, s in enumerate(S):
  if s == 'R':
    if S[i + 1] == 'L':
      UH[i] += 1
  else:
    if S[i - 1] == 'R':
      UH[i - 1] += 1
UH[0] = min(UH[0], 1)
UH[N] = min(UH[N], 1)
UH.sort(reverse=True)
for i in range(K):
  UH[i] = 0
if sum(UH) == 0:
  UH[0] = 1
print(N - sum(UH))

Submission status: Runtime Error

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

s = input()

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

ans = n-1
tmp = 0
for i in range(n-1):
    if s[i] != s[i+1]:
        ans -= 1
        
ans += 2*k
print(min(ans,n-1))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
S = list(input())
i = 1
while K >= 1 and i < N:
    if S[i] != S[0]:
        while i<N and S[i] != S[0]:
            S[i] = S[0]
            i += 1
        K -= 1
    i += 1
ans = 0
for i in range(1,N-1):
    if S[i] == "L" and S[i-1] == "L":
        ans += 1
    elif S[i] == "R" and S[i+1] == "R":
        ans += 1
if S[0] == "R" and S[1] == S[0]:
    ans += 1
if S[-1] == "L" and S[-2] == S[-1]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=input()
hap=0
for i in range(n):
  if(i==0):
    if(s[0]==s[1]=='R'):
      hap+=1
  elif(i==n-1):
    if(s[n-2]==s[n-1]=='L'):
      hap+=1
  else:
    if(s[i]==s[i+1]=='R' or s[i-1]==s[i]=='L'):
      hap+=1
print(min(hap+2*k,n-1))