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