Page Contents

*Bob and Canada Solution*

*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.

See Also : Canada Day Contest 2021

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.

#### Constraints

1≤T≤10001≤T≤1000

Subtask | Score | Constraints |
---|---|---|

1 | 5% | 3≤n≤103≤n≤10, the sum of nn across all strings will not exceed 1000010000 |

2 | 20% | 3≤n≤20003≤n≤2000, the sum of nn across all strings will not exceed 1000010000 |

3 | 75% | 3≤n≤7500003≤n≤750000, the sum of nn across all strings will not exceed 750000750000 |

#### 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.