Problem link:- https://mycode.prepbytes.com/problems/strings/STRGME
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t ; cin>>t;
for(int i=0;i<t;i++)
{
int n ; cin>>n; int ans=0;
string str ; cin>>str ;
int flag=1; // flag will be 0 when tere is no error in the string
while(flag==1)
{ int flag=0;
int loc=-1 ; int error;
for(int g=0;g<str.length()-1;g++)
{
if(str[g]==str[g+1])
{
loc=g;
error=str[g];
flag=1;
break;
}
}
if(flag==0)
{
//cout<<"flag is 0"<<endl;
break;
}
ans++;
//longest correct sequence after the error
int flag1=0,flag2=0; int end=-1,g; // flag1 will indicate if we got the correct char
for(g=loc+1;g<str.length()-1;g++)
{
if(str[g]!=error) flag1=1;
if(str[g]!=error) { end=g; }
if((flag1==1)&&(str[g]==str[g+1]))
{ flag2=1;break;}
}
if((flag2==0)&&(str[g]!=error))
{
end=g;
}
// cout<<"loc and end is "<<loc<<" "<<end<<endl;
int size = end-(loc+1)+1 ;
int limit =(loc+1)+size/2; int down =0,start=loc+1;
while(start<limit)
{
char temp1=str[start];
char temp2=str[end-down];
//cout<<"start and end-down is "<<start<<" "<<end-down<<endl;
str[start]=temp2; str[end-down]=temp1;
down++;
start++;
}
//cout<<"value of str "<<str<<endl;
}
cout<<ans<<endl;
}
return 0;
}