cant pass all cases any suggestions ?
String Window test cases
You are logically correct you just need to take all cases according. Take it as a reference and see if it helps.
string findSubString(string str, string pat)
{
int len1 = str.length();
int len2 = pat.length();
// check if string's length is less than pattern's
// length. If yes then no such window can exist
if (len1 < len2)
{
cout << "No such window exists" ;
return "" ;
}
int hash_pat[no_of_chars] = {0};
int hash_str[no_of_chars] = {0};
// store occurrence ofs characters of pattern
for ( int i = 0; i < len2; i++)
hash_pat[pat[i]]++;
int start = 0, start_index = -1, min_len = INT_MAX;
// start traversing the string
int count = 0; // count of characters
for ( int j = 0; j < len1 ; j++)
{
// count occurrence of characters of string
hash_str[str[j]]++;
// If string's char matches with pattern's char
// then increment count
if (hash_pat[str[j]] != 0 &&
hash_str[str[j]] <= hash_pat[str[j]] )
count++;
// if all the characters are matched
if (count == len2)
{
// Try to minimize the window i.e., check if
// any character is occurring more no. of times
// than its occurrence in pattern, if yes
// then remove it from starting and also remove
// the useless characters.
while ( hash_str[str[start]] > hash_pat[str[start]]
|| hash_pat[str[start]] == 0)
{
if (hash_str[str[start]] > hash_pat[str[start]])
hash_str[str[start]]--;
start++;
}
// update window size
int len_window = j - start + 1;
if (min_len > len_window)
{
min_len = len_window;
start_index = start;
}
}
}
// If no window found
if (start_index == -1)
{
cout << "No such window exists" ;
return "" ;
}
// Return substring starting from start_index
// and length min_len
return str.substr(start_index, min_len);
}
in your approach you are first getting your window then contracting it, while I am getting all the contracting substrings and storing them finally printing the smallest one. I think I have covered all the cases, please tell me modification in my code
contracted substrings***
Both the approaches are correct if you are able to code it. I do not know some things which you have done in your code so It would be better for you to see where it fails. Can you tell me how many test cases are failing for you?
I’m getting 30/100, in this ques does characters of pattern have to be in same order in the calculated substring ?
Yes the substring must be same.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.