➤ Problem Link : 1187B. Letters Shop
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
bool fun(vector <int> v,vector<int> mp)
{
for(char i='a';i<='z';i++)
{
if(mp[i-'a']>v[i-'a'])
return 0;
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
vector<vector<int> > v(n);
for(char c='a';c<='z';c++)
{
v[0].push_back(0);
}
v[0][s[0]-'a']=1;
for(int i=1;i<n;i++)
{
for(char c='a';c<='z';c++)
v[i].push_back(v[i-1][c-'a']);
v[i][s[i]-'a']++;
}
int m;
cin>>m;
vector<int> mp;
while(m--)
{
string t;
cin>>t;
mp.clear();
for(char c='a';c<='z';c++)
mp.push_back(0);
for(int j=0;j<t.length();j++)
mp[t[j]-'a']++;
int low=0;
int high=n-1;
int mid;
while(low<high)
{
mid=low+(high-low)/2;
if(fun(v[mid],mp))
high=mid;
else
low=mid+1;
}
cout<<low+1<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.