Whats the problem with this non hashing approach for this question : String Window

#include<bits/stdc++.h>
using namespace std;

class compare{
public:
bool operator()(pair<int,int> a, pair<int,int> b){
return ((a.second-a.first)>(b.second-b.first));
}
};

bool confirm(string ans, string b){
int k=0;
for(int i=0; i<ans.size();i++){
// checking if every element of b is in ans
if(ans[i]==b[k])
++k;
}

if(k==b.size())
    return true;

else return false;

}
int main() {

string a, b;

getline(cin, a);
getline(cin, b);

if(b.size()>a.size()){
    cout<<"No string"<<endl;
}


if(b.size()==0){
    cout<<"No string"<<endl;
    return 0;
}

if (b.size() == 1) {

    if((a.find(b[0]))!=-1){
        cout << b << endl;
        exit(0);
    }
    else if((a.find(b[0]))==-1){
        cout<<"No string"<<endl;
        exit(0);
    }

}

pair<int,int>pr;

char beg = b[0];
char end = b[b.size()-1];

priority_queue<pair<int,int>,vector<pair<int,int> >,compare> p;

int i=-1;
while(true){

// if(i==0){
int findexbeg =a.find(beg,i+1);
int findexend =a.find(end,findexbeg+1);
// making pairs of start and end indices of all possible occurences

    pr.first=findexbeg;
    pr.second=findexend;

    if(findexbeg!=0)
    i=findexbeg;
    else
        i=findexend;



    if((findexbeg==-1 || findexend==-1) && p.empty()){
        cout<<"No string"<<endl;
        exit(0);
    }

    if((findexbeg==-1 && !p.empty())||findexbeg>findexend)
        break;

   // p.push(a.substr(findexbeg,(findexend-findexbeg)+1));
    p.push(pr);

   // a.erase(0,findexend+1);


}

/* if(b.find(’ ')!=-1){
while(!p.empty()){
int f = p.top().first;
int e =p.top().second;

        string ans=a.substr(f,e-f+1);

        if(ans.find(' ')!=-1) {
            cout << ans << endl;
           exit(0);
        } else
            p.pop();
    }

    cout<<"No string"<<endl;

}
else if(b.find(' ')==-1){

int f = p.top().first;
int e =p.top().second;

cout<<a.substr(f,e-f+1)<<endl;

}
*/

while(!p.empty()){
int f = p.top().first;
int e =p.top().second;

   string ans=a.substr(f,e-f+1);

   if(confirm(ans,b)) {
       cout << ans << endl;
       break;
   }

   else
       p.pop();

}

if(p.empty()){
cout<<“No string”<<endl;
}
return 0;
}

Please add the problem link.

problem link: https://online.codingblocks.com/player/10033/content/5389
code link: https://ide.codingblocks.com/s/43520

CASE:
querty
teq

EXPECTED OUTPUT: quert
YOUR OUTPUT: No string.

This is because you assumed that order of string B matters. The question says find a subtring that contains all characters of second string (This does not mean in the order they are given).

Secondly, your approach hash complexity O(N^2). Hashing will solve this in O(N*26).

Try it out and let me know in case of any issues.

1 Like

I have written this code https://ide.codingblocks.com/s/72850.
i am not able to understand how to obtain the shortest possible substring (my code is computing the largest possible substring).
Can you please explain or atleast give a hint on the approach ?

@S18LPC-OL0076

please create a new thread so that we can help in a appropriate manner.

I have created a new thread for this, and invited you there. Please reply

Hi

yeah Sure I’ll see it.