Canada Day Contest 2021 - Bob and Canada

View as PDF

Submit solution


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, the number of strings.

Then T test cases follow. Each contains a single integer n on its own line, the length of the string, and a string 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

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

Sample Input

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

Sample Output

0
2
2
1
1
3
1
3

Explanation

Here is a possible result for each string:

RWR
RWR
RWR
RWWR
RWWRRR
RRRRWR
RRRRWWRRRR
RRRRWWWWRR

Comments

There are no comments at the moment.