Canada Day Contest 2021 - Bob and Canada - Olympiads Online Judge

Canada Day Contest 2021 - Bob and Canada

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 256M

Authors:

Problem type

Bob has a collection of strings. Each string consists of the characters R and W. He considers a string to be Canadian if it can be split into three nonempty, contiguous segments of Rs, Ws, and Rs, in that order.

canadad

Here are some examples of Canadian flags: RWR, RRWWRR, RRRRWRR.
Examples of strings that are not Canadian flags: RWW, RRRRR, RWRW.

For each string in Bob's collection, find the minimum number of characters that must be changed to make the string Canadian.

Input Specification

The first line will contain $T$ ~T~, the number of strings.

Then $T$ ~T~ test cases follow. Each will contain a single integer $n$ ~n~ on its own line, the length of the string, and a string $s$ ~s~.

Output Specification

For each string in Bob's collection, find the minimum number of characters that must be changed to make the string Canadian.

Constraints

$1 \le T \le 1000$ ~1 \le T \le 1000~

Subtask	Score	Constraints
1	5%	$3 \le n \le 10$ ~3 \le n \le 10~, the sum of $n$ ~n~ across all strings will not exceed $10\,000$ ~10\,000~
2	20%	$3 \le n \le 2\,000$ ~3 \le n \le 2\,000~, the sum of $n$ ~n~ across all strings will not exceed $10\,000$ ~10\,000~
3	75%	$3 \le n \le 750\,000$ ~3 \le n \le 750\,000~, the sum of $n$ ~n~ across all strings will not exceed $750\,000$ ~750\,000~

Sample Input

8
3
RWR
3
WWW
3
WRR
4
RWRW
6
WWWRRR
6
WWRRWW
10
RRRRWWRWRR
10
WWRRWWWWRW

Sample Output

Explanation

Here is a possible result for each string:

RWR
RWR
RWR
RWWR
RWWRRR
RRRRWR
RRRRWWRRRR
RRRRWWWWRR

Comments

2

PhoenixCoolIce commented on April 19, 2024, 8:20 p.m.

O Canada! Our home and native land! True patriot love in all of us command. With glowing hearts we see thee rise, The True North strong and free! From far and wide, O Canada, we stand on guard for thee. God keep our land glorious and free! O Canada, we stand on guard for thee. O Canada, we stand on guard for thee.