PROBLEM LINK:
Author: Chandan Boruah
Tester: Taranpreet Singh
Editorialist: TaranPreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Greedy
PROBLEM:
Given N balls, each ball colored either red or blue, we have to find maximum number of green balls we can make. A Green ball can be made by merging consecutive red and blue ball.
QUICK EXPLANATION
 Final composition of balls would never have consecutive balls are red and blue, since we can always merge them to obtain one more green ball.

So, merging balls greedily would generate maximum number of green balls.
EXPLANATION
All we need to do is to merge red and blue ball whenever we find a pair of such balls. All we need to prove now is that this approach is optimal.
Consider example: RBRB
Here, if we choose to merge second and third ball, our final compostion would look something like this RGB. Since we cannot move Green ball from inbetween, we cannot merge the remaining red and blue ball. This proves that we should perform the merge operation as early as possible, otherwise Green ball might block future merge operation.
Instead of pair (2, 3), had we chosen (1, 2), we can still merge (3, 4) getting 2 green balls in the end, thus, being the optimal approach for merging.
Complexity:
Time Complexity is O(N).
AUTHORâ€™S SOLUTIONS:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int tests=int.Parse(Console.ReadLine());
for(int k=0;k<tests;k++)
{
int t=int.Parse(Console.ReadLine());
string s=Console.ReadLine();
int max=0;
int count=0;
for(int i=0;i<t1;)
{
if(s*!=s[i+1]){count++;i+=2;}
else i++;
}
max=count;
count=0;
for(int i=1;i<t;)
{
if(s*!=s[i1]){count++;i+=2;}
else i++;
}
max=Math.Max(count,max);
Console.WriteLine(max);
}
}
}