Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
2,882 views
Example input :

3
aaaaaagaaaaaaaaa
abacda
bbaaabcbeea

Output :

15
3
6
in Algorithms and Problems by Expert (107,550 points) | 2,882 views

1 Answer

0 like 0 dislike

My code for the same : 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 

int main() 
{
    ll t; 
    cin>>t;
    while(t--)
    {
        string s ; 
        cin>>s;
        ll n = s.size();
        ll a[n]={0};
        ll start = -1;
        ll end = -1;
        ll i = 0 ; ll c = 0 ; 
        while(i<n)
        {
            if(s[i]!='a' && s[i]!='e' && s[i]!='o' && s[i]!='u' && s[i]!='i')
            {
                if(c==0)
                {
                    start = i ; 
                }
                end = i ; 
                a[i] = 1  ; 
                c++;
            }
            i++;
        }
        ll prefix[n]={0};
        prefix[0] = -1;
        i = 0 ; 
        while(i<n)
        {
            if(a[i]==1)
            {
                prefix[i] = i ;     
            }
            else
            {
                if(i>=1){
                prefix[i] = prefix[i-1];
                }
            }
            i++;
        }
        ll suffix[n]={0};
        suffix[n-1] = -1;
        i = n - 1 ; 
        while(i>=0)
        {
            if(a[i]==1)
            {
                suffix[i] = i ;     
            }
            else
            {
                if(i<=n-2){
                suffix[i] = suffix[i+1];
                }
            }
            i--;
        }
        //cout<<start<<" "<<end<<'\n';
        ll maxi = 0 ; 
        
        
        if(start==-1)
        {
            maxi = n ; 
        }
        else
        {
        ll i1 = start ; 
            while(i1<=end)
            {
                ll l1 = start ; 
                ll l2 = prefix[i1];
                ll length = abs(l1-l2)+1;
                ll length2 = 0 ; 
                if(end>=i1+1){
                ll l3 = end ; 
                ll l4 = suffix[i1+1];
                length2 = abs(l3-l4)+1;
                }
                
                ll tot_length = length + length2 ; 
                ll answer = n - tot_length ; 
                //cout<<tot_length<<endl;
                maxi = max(answer,maxi);
                i1++;
            }
        }
        cout<<maxi;cout<<'\n';
    }
    return 0 ; 
}
by Expert (107,550 points)