The above is the link to the problem. I have written a solution using upper_bound function which is getting TLE for 2 out of 13 test cases and barely passing one 1 testcase. Any help in either reducing time in my code or telling the solution will not be accepted with this method will be appreciated. Thank you.(I have put comments in my code to help in understanding.)
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
void solve(){
int n,m;
string s;
cin>>n>>s>>m;
//Values is like a 2d vector which stores all the occurences of a in val[0], that of b in val[1],etc
//I also put a value n at the end of all the alphabets to mark a end point.
//indexes a zero based index
vector<vector<int>> values(26);
for(int i=0;i<n;i++){
values[s[i]-'a'].push_back(i);
}
for(int i=0;i<26;i++){
values[i].push_back(n);
}
//In the above two loop i have filled values vector with all the indexes of all the alphabets
//Note : All the occurences are sorted and there is a end point n present in all the vectors
//containing the occurencesof each element.
//I am initially setting my solution as INT_MAX so if i have a solution lower then this by the end
//of the program i will print that solution(lowest answer) else i will print -1.
int sol=INT_MAX;
//We always have to start our subsequences with the letter a so i have decided that i will create
//a loop with in which i try to find all the answers which start with each occurences of a.
for(int i=0;i<values[0].size()-1;i++){
//The temp variable is just to there to check the size of the subsequence will be m.
int temp=m-1;
//K is used to identify the position of the alphabet i will be finding next (k%26).
//K is one since we already have a.
int k=1;
//Start is the position of the alphabet a from which we are going to find our answer/subsequence.
int start=values[0][i];
//If there are not enough element in the string to find a answer we get out of loop.
if(start+m-1>=n)
break;
//In the beginning we name end=start as the subsequence we have found till now is only till position start
int end=start;
//In this loop we will find all m element of the subsequence
while(temp!=0){
//D is the alphabet to find.
int d=k%26;
//it iterator gives us the alphabet we need to find and we put the position of this alphabet in
//end.Note we find upper_bound to end as end was the position of our last element
auto it=upper_bound(values[d].begin(),values[d].end(),end);
end=values[d][it-values[d].begin()];
//If end==n we won't able to complete thi subsequence or any new subsequence so we
//can finish the program here.
if(end==n){
if(sol==INT_MAX){
cout<<-1<<"\n";
return;
}
//SInce we need to print the total numbers to deleted it is sol-m
cout<<sol-m<<"\n";
return;
}
//If before finding all the element,we find that the current to be solution is
//greater then actual solution, we can skip this partcular subsequence.
if(end-start+1>=sol){
break;
}
temp--;
k++;
}
//if end<n i.e there is a soolution
if(end!=n)
sol=min(sol,end-start+1);
//No other soolution is smaller then this so we can end.
if(sol==m)
break;
}
//This is discussed above.
if(sol==INT_MAX){
cout<<-1<<"\n";
return;
}
cout<<sol-m<<"\n";
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
Code without comments
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
void solve(){
int n,m;
string s;
cin>>n>>s>>m;
vector<vector<int>> values(26);
for(int i=0;i<n;i++){
values[s[i]-'a'].push_back(i);
}
for(int i=0;i<26;i++){
values[i].push_back(n);
}
int sol=INT_MAX;
for(int i=0;i<values[0].size()-1;i++){
int temp=m-1;
int k=1;
int start=values[0][i];
if(start+m-1>=n)
break;
int end=start;
while(temp!=0){
int d=k%26;
auto it=upper_bound(values[d].begin(),values[d].end(),end);
end=values[d][it-values[d].begin()];
if(end==n){
if(sol==INT_MAX){
cout<<-1<<"\n";
return;
}
cout<<sol-m<<"\n";
return;
}
if(end-start+1>=sol){
break;
}
temp--;
k++;
}
if(end!=n)
sol=min(sol,end-start+1);
if(sol==m)
break;
}
if(sol==INT_MAX){
cout<<-1<<"\n";
return;
}
cout<<sol-m<<"\n";
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
