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:
def A(string):
  cnt = 0
  temp = 0
  for i in string:
    if i == temp:
      cnt += 1
    temp = i
  return cnt

N, K = [int(i) for i in input().split()]
S = input()
cnt1 = 0
cnt2 = 0
for i in range(len(S)-1):
  if S[i] != S[i+1]:
    if S[i]=="R":
      cnt1+=1
    else:
      cnt2+=1
a = A(S)
b = cnt1//2+cnt2//2
if K > b:
  if cnt1%2 == 1 or cnt2%2 == 1:
    print(a+b*2+1)
  else:
    print(a+b*2)
else:
  print(a+K*2)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
#LR数できまる.
#両側が同じときはさらにもう一つ減る
LR = 0
f = 0
for j in range(N-1):
    if S[j] == "L" and S[j+1]== "R":
        if j == 0 or j == N-2:
            f += 1
        else:
            LR += 1

if LR > K:
    ans = N - (LR-K)*2
elif f > K-LR:
    ans = N -(f+LR-K)*2
else:
    ans = N-1

print(ans)

Submission status: Wrong Answer

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

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

ans = N-len(ranlength_l)
for const in (ranlength_l[1:-1:2]):
    if(K==0):
        break
    ans += 2
    K = K-1

if(K!=0 and len(ranlength_l)!=1):
    ans+=1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
 
n, k = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
 
init_val = 0
for i in range(len(s)):
  if s[i] == 'L' and i-1 > 0 and s[i-1] == 'L': init_val += 1
  elif s[i] == 'R' and i+1 < n and s[i+1] == 'R': init_val += 1
print(min(init_val+2*k, n-1))

Submission status: Wrong Answer

Solution code:
# coding: utf-8


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

    # initialize
    output = 0
    if S[0] == "R" and S[1] == "R":
        output += 1
    for i in range(1, N-1):
        if S[i] == "L":
            if S[i-1] == "L":
                output += 1
        elif S[i] == "R":
            if S[i+1] == "R":
                output += 1
    if S[N-1] == "L" and S[N-2] == "L":
        output += 1

    k = 0
    i = 0
    while i < N-2:
        if S[i] == S[i+1]:
            i += 1
            continue
        start = S[i]
        for j in range(i+2, N):
            if S[j] == start:
                i = j
                k += 1
                output += 2 if j < N-1 else 1
                if k == K:
                    return output
                break
            if j == N-1:
                return N - 1

    return output


if __name__ == "__main__":
    output = main()
    print(output)

Submission status: Wrong Answer

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

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

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

if score > N:
    print(N-1)
else: 
    print(score-1)

Submission status: Wrong Answer

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

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

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

if score > N:
    print(N-2)
else: 
    print(score)

Submission status: Wrong Answer

Solution code:
import math
input = raw_input

def score(s):
    n = len(s)
    ans = 0
    for i in range(n):
        if s[i] == "L" and i >= 1 and s[i-1] == "L":
            ans += 1
        elif s[i] == "R" and i <= n-2 and s[i+1] =="R":
            ans += 1
    return ans

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

if S=="RL":
    print(0)
    exit()
if S=="LR":
    print(0)
    exit()
if S=="RLR" or S=="LRL":
    if K == 1:
        print(1)
        exit()
    else:
        print(2)
        exit()

s = score(S)
k = 0
lr = 0
rl = 0
for i in range(N-1):
    if S[i] == "L" and S[i+1] =="R":
        lr += 1
    if S[i] == "R" and S[i+1] =="L":
        rl += 1
lrl = 0
rlr = 0
for i in range(N-2):
    if S[i] == "L" and S[i+1] =="R" and S[i+2] =="L":
        lrl += 1
    if S[i] == "R" and S[i+1] =="L" and S[i+2] =="R":
        rlr += 1

if (lrl == 1 and rl == 1 and lr == 1) or (rlr == 1 and rl == 1 and lr == 1):
    if K >= 2:
        print(s+2)
        exit()
    elif K == 1:
        print(s+1)
        exit()
    else:
        print(s)
        exit()

#print(s)
#print(lr, rl)
c = min(K, lr, rl)
s += 2 * c
K -= c

if S[0] == "L" and lr < rl and K > 0:
    s += 1
elif S[-1] == "R" and rl < lr and K > 0:
    s += 1
print(s)

Submission status: Wrong Answer

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

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

ans = N-len(ranlength_l)
for const in range((len(ranlength_l)-2)//2):
    if(K==0):
        break
    ans += 2
    K = K-1

if(K!=0 and len(ranlength_l)!=1):
    if(K>=2):
        ans+=2
    else:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
RL = 0
RL_L = 0
RL_R = 0

if S[0] == 'L':
    RL_L += 1

if S[N-1] == 'R':
    RL_R += 1


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

# print(RL_L, RL, RL_R)

if RL != 0:
    while (K > 0):
        if RL != 0:
            RL -= 2
            K -= 1

if RL_L == 1 and K > 0:
    RL_L -= 1
    K -= 1

if RL_R == 1 and K > 0:
    RL_R -= 1

ans = N - (RL + RL_L + RL_R)

print(ans)

Submission status: Wrong Answer

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

counts = []

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

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
s = input()
gn = 1
for i in range(n-1):
    gn += s[i] != s[i+1]

print(n - 1 if gn <= 2 else n - (gn - k*2))

Submission status: Wrong Answer

Solution code:
import sys

N, K = (int(x) for x in input().split())
S = list(input())

answer = 0

for k in range(K):                                                                                                                                                                                          
    ini = S[0]                                                                                                                                                                                              
    tmp_answer = 0                                                                                                                                                                                          
    l = 0                                                                                                                                                                                                   
    r = 0                                                                                                                                                                                                   
                                                                                                                                                                                                            
    for i in range(N):                                                                                                                                                                                      
        if S[i] != ini:                                                                                                                                                                                     
            l = i                                                                                                                                                                                           
            break                                                                                                                                                                                           
                                                                                                                                                                                                            
    for j in range(N):                                                                                                                                                                                      
        if S[N-1-j] != ini:                                                                                                                                                                                 
            r = N-1-j                                                                                                                                                                                       
            break                                                                                                                                                                                           
                                                                                                                                                                                                            
                                                                                                                                                                                 
                                                                                                                                                                                 
                                                                                                                                                                                                            
    for k in range(r-l):                                                                                                                                                                                    
        if l+k < r-k:                                                                                                                                                                                       
                                                                                                                                                                            
                                                                                                                                                                          
            tmp = S[l+k]                                                                                                                                                                                    
            S[l+k] = S[r-k]                                                                                                                                                                                 
            S[r-k] = tmp                                                                                                                                                                                    
            if S[l+k] == 'L':                                                                                                                                                                               
                S[l+k] = 'R'                                                                                                                                                                                
            else:                                                                                                                                                                                           
                S[l+k] = 'L'                                                                                                                                                                                
            if S[r-k] == 'L':                                                                                                                                                                               
                S[r-k] = 'R'                                                                                                                                                                                
            else:                                                                                                                                                                                           
                S[r-k] = 'L'                                                                                                                                                                                
        elif l+k == r-k:                                                                                                                                                                                    
            if S[l+k] == 'L':                                                                                                                                                                               
                S[l+k] = 'R'                                                                                                                                                                                
            else:                                                                                                                                                                                           
                S[l+k] = 'L'                                                                                                                                                                                
        else:                                                                                                                                                                                               
            break                                                                                                                                                                                           
                                                                                                                                                                                                 
    for l in range(0, N):                                                                                                                                                                                   
        if l > 0:                                                                                                                                                                                           
            if S[l] == S[l-1]:                                                                                                                                                                              
                if S[l] == 'L':                                                                                                                                                                             
                    tmp_answer += 1                                                                                                                                                                         
        if l < N -1:                                                                                                                                                                                        
            if S[l] == S[l+1]:                                                                                                                                                                              
                if S[l] == 'R':                                                                                                                                                                             
                    tmp_answer += 1    
    if answer < tmp_answer:                                                                                                                                                                                 
        answer = tmp_answer                                                                                                                                                                                 
    else:                                                                                                                                                                                                   
        print(tmp_answer)                                                                                                                                                                                   
        sys.exit()                                                                                                                                                                                          

print(answer)

Submission status: Wrong Answer

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

if n == 1:
        print(0)
else:        
        t = []
        tt = 0
        ss = s[0]
        for i in range(1,n):
                if s[i] != ss:
                        t.append(i - tt)
                        tt = i
                        ss = s[i]
        t.append(n - tt)
        cnt = sum(t) - len(t) 

        if len(t) % 2 == 0:
                if k <= (len(t) - 2)/2:
                        cnt += 2 * k
                else:
                        cnt += 2 * (len(t) - 2)/2 + 1
        else:
                if k <= (len(t) - 1)/2:
                        cnt += 2 * k
                elif k == (len(t) - 1)/2 + 1:
                        cnt += 2 * k + 1
                else:
                        cnt += 2 *(len(t) - 1)/2 + 2
        print(int(cnt))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=input()
p=0
for i in range(n-1):
    if a[i]==a[i+1]:
        p+=1
print(min(p+2*k,n-n%2))

Submission status: Wrong Answer

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

for j in range(N-1):
    if S[j] == "L" and S[j+1]== "R":
        LR += 1
'''
if LR > K:
    ans = N - (LR-K)*2
else:
    ans = N-1
'''
ans = min(N-1, N - (LR-K)*2)

print(ans)

Submission status: Wrong Answer

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

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

current = 0
for i in range(0, K):
  l_RL_index = -1
  l_LR_index = -1
  r_RL_index = -1
  r_LR_index = -1
  for j in range(current, N-1):  
    if S[j] == "R" and S[j+1] == "L":
      if l_RL_index == -1:
        l_RL_index = j + 1
      if l_LR_index != -1:
        r_RL_index = j
    elif S[j] == "L" and S[j+1] == "R":
      if l_LR_index == -1:
        l_LR_index = j + 1
      if l_RL_index != -1:
        r_LR_index = j
    
    if l_RL_index != -1 and r_LR_index != -1:
      S = swap_list(S, l_RL_index, r_LR_index)
      break
    elif l_LR_index != -1 and r_RL_index != -1:
      S = swap_list(S, l_LR_index, r_RL_index)
      break
  
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: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,K = [int(x) for x in  input().split()]
S = list(input())
ans = [0]
a = []
for i in range(N-1):
  if S[i]!=S[i+1]:
  	ans.append(i)
ans.append(N-1)
#print(ans)
a = []
for i in range(1,len(ans)):
  a.append(ans[i]-ans[i-1])
a[0] +=1
ans2 = sum(a)-len(a)
#print(a)
#print(ans2)
if len(a)!=1:
  ans2 = ans2 +(2*K if len(a)*(len(a)+1)//2>K else len(a)*(len(a)+1)//2*2)
  if len(a)-K>=1:
    ans2 -=1
  print(ans2)
  exit()
print(ans2)

Submission status: Wrong Answer

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

ans = K
streak = 1

for i in range(N-1):
    if S[i] == S[i+1]:
        streak += 1
    else:
        if streak > 1:
            ans += streak
            streak = 1

if streak > 1:
    ans += streak

if S.startswith("LL"):
    ans -= 1
if S.endswith("RR"):
    ans -= 1

print(min(ans, N-1))

Submission status: Wrong Answer

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

conti = 0

if n == 1:
    print(0)
else:
    for i in range(n-1):
        if s[i] == s[i+1]:
            conti += 1
        
count = min(n-1, conti+2*k)
print(count)

Submission status: Wrong Answer

Solution code:
# sys.stdin.readline
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        S = input().rstrip()

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

        c = 2 * K + 1
        if len(b) <= c:
            print(sum(b) - 1)
            exit()

        print(sum(b) - (len(b) - c + 1))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

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

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

ans = N-len(ranlength_l)
for const in (ranlength_l[1:len(ranlength_l)-1][::2]):
    if(K==0):
        break
    ans += 2
    K = K-1

if(K!=0 and len(ranlength_l)!=1):
    if(K>=2):
        ans+=2
    else:
        ans+=1

print(ans)

Submission status: Wrong Answer

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

c = 0
p = 0
for i, s in enumerate(S):
    if i == 0:
        pres = s
    elif s != pres:
        c += 1
    else:
        p += 1
if c == 0 or c == 1 or c <= 2*(K-1):
    ans = N-1
else:
    ans = p+2*(K-1)
print(ans)

Submission status: Wrong Answer

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

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

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


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

left, right = [], []
current = 0
l_happy, r_happy = 0, 0
for i, (s0, s1) in enumerate(zip(s, s[1:]), 1):
    if s0 != s1:
        dst, len_ = s0, i - current
        current = i
        if dst == 'L':
            heapq.heappush(left, (-len_, i == 1))
            l_happy += len_ - 1
        else:
            heapq.heappush(right, (-len_, i == 1))
            r_happy += len_ - 1
if s[-1] == 'L':
    heapq.heappush(left, (-(len(s) - current), True))
    l_happy += len(s) - current - 1
else:
    heapq.heappush(right, (-(len(s) - current), True))
    r_happy += len(s) - current - 1

if l_happy > r_happy:
    for _ in range(k):
        if right:
            len_, flag = heapq.heappop(right)
            l_happy += -len_ + (0 if flag else 1)
    print(min(l_happy, n - 1))
else:
    for _ in range(k):
        if left:
            len_, flag = heapq.heappop(left)
            r_happy += -len_ + (0 if flag else 1)
    print(min(r_happy, n - 1))