[Question](https://www.codechef.com/START24B/problems/SPECIALSTR)↵
↵
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;↵
}↵
↵
`~~~~~`↵
``↵
``↵
↵
↵
↵
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;↵
}↵
`
``
↵
↵
