W String

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