CHAIN STRING

• Problem Description

  
  Remo went to the shop to buy a chain for his girlfriend. The shopkeeper has shown him a chain made of some expensive stones. The chain has n stones marked from 0 to n-1. The ith stone is connected with ((i+1)%n)th stone for each 0 i < n. Each stone can be either Ruby or Amber.
  
  Nemo defines beauty factor B of a chain as the maximum number of consecutive stones of same type.
  
  Nemo wants to chose exactly one stone i and exchange it with a stone with different type. So if the ith stone is ruby, Nemo will exchange it with Amber and vice-versa. He wants to do it in such a way that the value B is as small as possible.
  
  Given the configuration of the chain, can you find the minimum value of B that Nemo can get after exchanging exactly one stone? Note that, Its not allowed to change positions of the stones, the new stone must be placed in the same position as the original stone.
  Input
  
  First line contains number of test cases T (1<= T <= 2500). For each test cases, there is a single line containing a string S (1 <= |S| <= 105) denoting the chain. Here |S| denotes the length or number of characters in the string. The string is made of only R (Ruby) and A (Amber). Total number of characters in the input file will be less than 5 x 106.
  Output
  
  For each test case, print the case number and the answer in a single line. Look at the output for sample input for details.
  

• CODING ARENA

• #include <stdio.h>

  #include<string.h>

  int main()

  {

    int p0,p1,p2,m1,m2,l,tl,single=0,t,i;

    scanf("%d",&t);

    char arr[100001];

    for(i=0;i<t;++i)

    {

      single=0;

      m1=0;m2=0;

      scanf("%s",arr);

      l=strlen(arr);

      p1=1;

      if(l==1)

        printf("%d\n",1);

      else

        

      {

        while(arr[0]==arr[p1])

          p1++;

        p0=p1;

        if(p1==l)

          printf("%d\n",l-1);

        else

        {

          do

          {

            tl=1;

            p2=p1;

            if(p2==l-1)

              p2=-1;

            while(arr[p1]==arr[p2+1])

            {

              tl++;

              p2++;

              if(p2==l-1)

                p2=-1;

            }

            if(tl==1)

              single++;

            if(tl>m2)

            {

              m2=tl;

              if(m2>m1)

              {

                m2=m1;

                m1=tl;

              }

            }

            p1=p2+1;

          }

          while(p1!=p0);

          if(m1>2)

          {

            m1=m1/2;

            if(m1>m2)

              printf("%d\n",m1);

            else

              printf("%d\n",m2);

          }

          else if(m1==2)

          {

            if(single>=1)

              printf("%d\n",2);

            else

              printf("%d\n",3);

          }

          else

          {

            if(l==2)

              printf("%d\n",2);

            else

              printf("%d\n",3);

          }

        }

      }

    }

    return 0;

  }

          

          

        

  
  

• Test Case 1

  
  Input (stdin)

  2
  
  RRRAAAARAA
  
  ARRRRAAA
  
  

  Expected Output

  3
  
  4

• Test Case 2

  
  Input (stdin)

  2
  
  RRAAAARA
  
  AAAAAARRA
  
  

  Expected Output

  2
  
  3