Codechef Starters 24 Special String
Разница между en1 и en2, 1,542 символ(ов) изменены
[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;↵
}↵

`~~~~~`↵
``↵
``↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский SagarPrasad 2022-02-03 11:39:45 12
en2 Английский SagarPrasad 2022-02-03 11:38:58 1542
en1 Английский SagarPrasad 2022-02-03 11:36:47 4207 Initial revision (published)