Magical Planks Fizzbuzz Solution | CodeChef Solution

Magical Planks Fizzbuzz Solution

Ryan is a boy from a small town, who has been given a task by his father. He has N wooden planks, numbered from 1 to N, which are colored either black or white.

His task is to color all planks the same color! But there is some magic in the winds of his small town. Whenever he colors the ith ( plank which has the color Si ) to a color P then following events happen:

if 2≤i≤N and Si=Si−1, then color of (i−1)th plank changes to P.
if 1≤i≤N−1 and Si=Si+1, then color of (i+1)th plank changes to P.
Now this process continues for the newly colored planks also. If none of the neighbors have same color, then nothing happens to the neighbors.

Suppose Ryan has planks which have their coloring : BBWWWB If Ryan colors the fourth plank( whose color is W ) to color B, then the finally the planks would be colored as following:

BBBBBB

Ryan can choose any one of the N planks and change its color as many times as he wants. Determine the minimum number of times Ryan has to paint a plank such that all planks get the same color at the end.
Input Format
First line will contain T, number of testcases. Then the testcases follow.
The first line of each test case consists of an integer N the number of planks
Second line of each test case consists of a string S of size N,where the i th character denotes the color of plank i
Output Format
For each testcase, output a single integer denoting the minimum number of times Ryan has to paint a single plank such that all planks get the same color at the end.
Constraints
1≤T≤105
1≤N≤105
S consists only of characters B and W
The sum of N over all cases doesn't exceed 105
Sample Input 1 
4
6
BBWWWB
5
WWBWB
2
BB
9
WWBBBBBWW
Sample Output 1 
1
2
0
1
Explanation
Test case 1: The first test case is already described in the question.

Test case 2: Ryan can paint the third plank to W. After doing so the color string of planks become WWWWB. Then he can again paint the third plank to the color B. After doing so the string goes through following transitions:

The color of third plank changes to B. ( The string becomes WWBWB )
The color of second and fourth plank changes to B. ( The string becomes WBBBB )
The color of first plank changes to B. ( The string becomes BBBBB )
Finally, all planks have same color.

Test case 3: All planks have the same color.

Test case 4: Ryan can paint any of the planks numbered from 3 to 7 to W, and all these planks will be colored to W!

Divide Students Into Classes Codechef Solution >>

Alphabet Difference Codechef Solution >>

Queries in an Array Codechef Solution >>

Get Registered in Contest

Leave a Reply

error: Content is protected !!