# Bob and Canada Solution | Canada Day Contest 2021

Page Contents

## Bob and Canada Solution

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.

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.

1≤T≤10001≤T≤1000

#### Input Specification

The first line will contain TT, the number of strings.

Then TT test cases follow. Each contains a single integer nn on its own line, the length of the string, and a string ss.

#### Output Specification

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

#### Sample Input

``````7
3
RWR
3
WWW
3
WRR
4
RWRW
6
WWWRRR
6
WWRRWW
10
RRRRWWRWRR``````

#### Sample Output

``````0
2
2
1
1
3
1``````

#### Explanation

Here is a possible result for each string:

``````RWR
RWR
RWR
RWWR
RWWRRR
RRRRWR
RRRRWWRRRR``````

Hint

In order to make a string Canadian, you need to change all the `W`s in the red sections and the `R`s in the white section.

Hint

Try to come up with a formula for the number of edits based on the starting point of the second and third section.

Solution

Lets say the first section (red) goes from index 11 to aa, the second (white) goes from a+1a+1 to bb, and the third (red) from b+1b+1 to nn. You can first try every combination of aa and bb. In order to count the number of Rs and Ws in a range quickly you can use a prefix sum array r[]r[] and w[]w[]. The answer for aa and bb will be (w[n]−w[b])+(r[b]−r[a])+(w[a])(w[n]−w[b])+(r[b]−r[a])+(w[a]). Looking at this formula you can notice that for any bb you should always choose the aa that minimizes r[a]−w[a]r[a]−w[a]. So as you loop through bb from 22 to n−1n−1, instead of checking every aa, you can just store the minimum value of r[a]−w[a]r[a]−w[a] so far. The time complexity will be O(n)O(n). There are quite a few other accepted solutions so feel free to show your own in the comments.