Problem:


Score : 400 points

Problem Statement

An altar enshrines N stones arranged in a row from left to right. The color of the i-th stone from the left (1 \leq i \leq N) is given to you as a character c_i; R stands for red and W stands for white.

You can do the following two kinds of operations any number of times in any order:

Choose two stones (not necessarily adjacent) and swap them.

Choose one stone and change its color (from red to white and vice versa).

According to a fortune-teller, a white stone placed to the immediate left of a red stone will bring a disaster. At least how many operations are needed to reach a situation without such a white stone?

Constraints

2 \leq N \leq 200000

c_i is R or W.

Input

Input is given from Standard Input in the following format:

N
c_{1}c_{2}...c_{N}

Output

Print an integer representing the minimum number of operations needed.

Sample Input 1

4
WWRR

Sample Output 1

2

For example, the two operations below will achieve the objective.

Swap the 1-st and 3-rd stones from the left, resulting in RWWR.

Change the color of the 4-th stone from the left, resulting in RWWW.

Sample Input 2

2
RR

Sample Output 2

0

It can be the case that no operation is needed.

Sample Input 3

8
WRWWRWRR

Sample Output 3

3



Sample input:
4
WWRR


Sample output:
2

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    c = S()
    dp1 = [0] * (n + 1)
    dp2 = [0] * (n + 1)
    W = c.count("W")
    R = c.count("R")
    for i in range(1, n + 1):
        dp1[i] = (c[i - 1] == "W") + dp1[i - 1]
        dp2[i] = (c[i - 1] == "R") + dp2[i - 1]
    ans = inf
    for i in range(n + 1):
        w = max(dp1[i], R - dp2[i], i - dp2[i])
        ans = min(ans, w)
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
C = list(input())
c = 0
top = 0
back = N-1
while top < back:
  if(C[top]=="W" and C[back]=="R"):
    c += 1
    C[top] = "R"
    C[back] = "W"
    top += 1
    back -= 1
  elif(C[top]=="W" and C[back]=="W"):
    back -= 1
  elif(C[top]=="R" and C[back]=="W"):
    top += 1
    back -= 1
  elif(C[top]=="R" and C[back]=="R"):
    top += 1
    
print(c)

Submission status: Accepted

Solution code:
N=int(input())
data=list(input())
r=data.count("R")
w=data.count("W")
last=[]
for i in range(r):
    last.append("R")
for i in range(w):
    last.append("W")
ans=0
for i in range(len(data)):
    if last[i]!=data[i]:
        ans+=1
print(int(ans/2))

Submission status: Accepted

Solution code:
N = int(input())
c = input()
cnt = 0
for char in c:
    if char == 'R':
        cnt += 1
cnt_loc = 0
for i in range(cnt):
    if c[i] == 'R':
        cnt_loc += 1
print(cnt - cnt_loc)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    c = list(S())

    left = 0
    right = N - 1
    ans = 0

    while True:
        if c[left] != 'W':
            left += 1
        if c[right] != 'R':
            right -= 1

        if left >= right:
            break

        if c[left] == 'W' and c[right] == 'R':
            c[left] = 'R'
            c[right] = 'W'
            ans += 1

        # print(left, right, c, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(input())
x = a.count('R')
b = a[:x]
print(b.count('W'))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = input()
W = deque([])
R = deque([])

for i in range(N):
    if S[i] == "W":
        W.append(i)
    else:
        R.appendleft(i)
#print(W)
#print(R)
ans = 0
while W and R:
    w = W.popleft()
    r = R.popleft()
    if w > r:
        break
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import math
    n = int(input())
    c = input()
    num = []
    r = 0
    w = 0
    for i in range(n):
        if c[i] == "R":
            r += 1
            num.append(0)
        else:
            w += 1
            num.append(1)
    fi = [0]*r+[1]*w
    ct = 0
    for i in range(n):
        if num[i] != fi[i]:
            ct += 1
    print(min(math.ceil(ct/2), w))
resolve()

Submission status: Accepted

Solution code:
n=int(input())
c=input()
r=c.count('R')
w=c.count('W')
rch=c[:r].count('W')
wch=c[r:].count('R')
print(min(rch,wch))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))

# For getting input from input.txt file
#sys.stdin = open('input.txt', 'r')

# Printing the Output to output.txt file
#sys.stdout = open('output.txt', 'w')


def main():
    n = inp()
    a = input()
    b = sorted(a)
    c = 0
    for i in range(n):
        if b[i] == "R" and a[i] != "R":
            c += 1
    print(c)


# region fastio
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
C = input()
len_r, len_w = 0, 0
for c in C:
    if c == 'R':
        len_r += 1
    else:
        len_w += 1
c2 = 'R'*len_r + 'W'*len_w
cnt = 0
for a, b in zip(C, c2):
    if a != b:
        cnt += 1
print(cnt//2)

Submission status: Accepted

Solution code:
n=int(input())
c=input()

r=0
w=0

for i in range(n):
    if c[i]=="R":
        r+=1
    else:
        w+=1

umeru=0

for j in range(r):
    if c[j]=="W":
        umeru+=1

if r>=umeru:
    print(umeru)
else:
    print(umeru + (r-umeru))

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())


r = 0
w = 0
w_num = 0


for i in s:
    if i == "R":
        r += 1


for j in s[0:r]:
    if j == "W":
        w_num += 1
print(w_num)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
red=s.count('R')
print(red-s[:red].count('R'))

Submission status: Accepted

Solution code:
n=int(input())
c=input()


a=c.count("R")
l=[c[i] for i in range(a)]
print(l.count("W"))