W String

• Problem Description

  
  Kira likes to play with strings very much. Moreover he likes the shape of W very much. He takes a string and try to make a W shape out of it such that each angular point is a # character and each sides has same characters. He calls them W strings.
  
  For example, the W string can be formed from "aaaaa#bb#cc#dddd" such as:
  
  a
  a d
  a # d
  a b c d
  a b c d
  # #
  He also call the strings which can generate a W shape (satisfying the above conditions) W strings.
  
  More formally, a string S is a W string if and only if it satisfies the following conditions (some terms and notations are explained in Note, please see it if you cannot understand):
  
  The string S contains exactly 3 # characters. Let the indexes of all # be P1 < P2 < P3 (indexes are 0-origin).
  Each substring of S[0, P11], S[P1+1, P21], S[P2+1, P31], S[P3+1, |S|1] contains exactly one kind of characters, where S[a, b] denotes the non-empty substring from a+1th character to b+1th character, and |S| denotes the length of string S (See Note for details).
  Now, his friend Ryuk gives him a string S and asks him to find the length of the longest W string which is a subsequence of S, with only one condition that there must not be any # symbols between the positions of the first and the second # symbol he chooses, nor between the second and the third (here the "positions" we are looking at are in S), i.e. suppose the index of the #s he chooses to make the W string are P1, P2, P3 (in increasing order) in the original string S, then there must be no index i such that S[i] = # where P1 < i < P2 or P2 < i < P3.
  
  Help Kira and he wont write your name in the Death Note

• CODING ARENA

• #include<stdio.h>

  #include<string.h>

  #include<malloc.h>

   

  //using namespace std;

  void program();

  char s[10003];

  int *max1, *max2, *max3;

  int k1=0;

   

  void fxn(int n)

  {

      int x[30]={0};

      int x2[30]={0};

      int x3[30]={0};

      int max=0,i,max_2=0,max_3=0;

      int j,k=0;

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

      {

          //printf("%c",s[i]);

          if(s[i]=='#')

          {

              max1[k]=max;

              max2[k]= max_2;

              for(j=0;j<30;j++) x2[j]=0;

              max_2=0;

              k++;

              continue;

          }

          x[s[i]-'a']++;

          x2[s[i]-'a']++;

          if(x2[s[i]-'a']>max_2)

          max_2= x2[s[i]-'a'];

   

          if(x[s[i]-'a']>max)

          max= x[s[i]-'a'];

      }

      k--;

      k1=k;

      for(i=n-1;i>=0;i--)

      {

          if(s[i]=='#')

          {

              max3[k]= max_3;

              k--;

              continue;

          }

          x3[s[i]-'a']++;

          if(x3[s[i]-'a'] >max_3)

          max_3= x3[s[i]-'a'];

      }

   

   

  }

  int main()

  {

      int t;

      scanf("%d",&t);

      while(t--)

      program();

      return 0;

  }

   

  void program()

  {

      //char s[10003];

      scanf("%s",s);

      //int x[30]= {0};

      int max=0,t,i,count=0;

      //vector<int> v;

      int n;

      for(i=0;s[i]!='\0';i++)

      {

          if(s[i]=='#')

          count++;

      }

      max1= (int*)malloc(sizeof(int)*count);

      max2= (int*)malloc(sizeof(int)*count);

      max3= (int*)malloc(sizeof(int)*count);

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

      {

          max1[i]=0;

          max2[i]=0;

          max3[i]=0;

      }

      n=strlen(s);

      max=0;

      fxn(n);

      int a,b,c,d;

      for(i=2;i<count;i++)

      {

        a= max1[i-2];

        b= max2[i-1];

        c= max2[i];

        d= max3[i];

         //printf("%d %d %d %d \n",a,b,c,d);

          if(a!=0 && b!=0 && c!=0 && d!=0)

          {

            t= a+b+c+d;

            if(t>max)

            max=t;

          }

      }

      if(max==0)

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

      else

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

  } 

• Test Case 1

  
  Input (stdin)

  1
  
  aaaaa#bb#cc#dddd
  
  

  Expected Output

  16

• Test Case 2

  
  Input (stdin)

  1
  
  acb#aab#bab#accba
  
  

  Expected Output

  10