### 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;
int *max1, *max2, *max3;
int k1=0;

void fxn(int n)
{
int x={0};
int x2={0};
int x3={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;
scanf("%s",s);
//int x= {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);
} ```