In this HackerEarth Vowel Query problem solution, You are given a string S consisting of lowercase alphabets and an integer array val consisting of N integers. Using the given string S and array val, you need to create another string X according to the code snippet below:

Initially string X is empty
Let len be the length of string S

for i := 0 to N-1
    pos := absolute value of val[i]
    if(val[i] >= 0)
      X := X + S[0,pos] // append substring of string S from index 0 to pos (both including) into X
    else
      X := X + S[pos,len-1] // append substring of string S from index pos to len-1 (both including) into X

You have to answer Q tasks. For each task, you are given an integer K and you have to print the Kth vowel in the string X. If the Kth vowel doesn't exist print -1.



HackerEarth Vowel Query problem solution


HackerEarth Vowel Query problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
string s;
ll q,n,val[100005],m,pre[100005],suf[100005],x;
vector<char>pref,suff;
vector<ll>cum;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll i,j,k;
cin>>s;
cum.push_back(0);
n=s.size();
cin>>m;
for(i=1;i<=m;i++)
{
cin>>val[i];
}
for(i=0;i<n;i++)
{
if(i>0)
pre[i]=pre[i-1];
if(s[i]=='a'||s[i]=='o'||s[i]=='e'||s[i]=='i'||s[i]=='u')
{
pre[i]++;
pref.push_back(s[i]);
}
}
suff=pref;
reverse(suff.begin(),suff.end());
for(i=n-1;i>=0;i--)
{
suf[i]=suf[i+1];
if(s[i]=='a'||s[i]=='o'||s[i]=='e'||s[i]=='i'||s[i]=='u')
{
suf[i]++;
}
}
for(i=1;i<=m;i++)
{
if(val[i]<0)
{
cum.push_back(cum[cum.size()-1]+suf[-1*val[i]]);
}
else
{
cum.push_back(cum[cum.size()-1]+pre[val[i]]);
}
}
cin>>q;
while(q--)
{
cin>>x;
if(cum[cum.size()-1]<x)
{
cout<<"-1\n";
}
else
{
j=lower_bound(cum.begin(),cum.end(),x)-cum.begin();
x-=cum[j-1];
j=val[j];
if(j<0)
{
j=suf[-j]-x;
cout<<suff[j]<<"\n";
}
else
{
x--;
cout<<pref[x]<<"\n";
}
}
}
return 0;
}