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

• 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

• Program

• #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);
  }