Bob and Canada Solution | Canada Day Contest 2021

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

Bob and Canada Solution | Canada Day Contest 2021

Here are some examples of Canadian flags: RWRRRWWRRRRRRWRR.
Examples of strings that are not Canadian flags: RWWRRRRRRWRW.

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

SubtaskScoreConstraints
15%3≤n≤103≤n≤10, the sum of nn across all strings will not exceed 1000010000
220%3≤n≤20003≤n≤2000, the sum of nn across all strings will not exceed 1000010000
375%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 Ws in the red sections and the Rs 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.

Leave a Comment