This code fails in two test cases - test case 3 & 8.
Could any one please help me in debugging the issue?
Thanks,
Arun
#include <bits/stdc++.h>
using namespace std;
string
findSubString(string& sourceString, string& patternString)
{
if (patternString.size() > sourceString.size())
{
cout << “No such string exists”;
return “”;
}
unsigned int sourceStringHash[256] = { 0 };
unsigned int patternStringHash[256] = { 0 };
for (unsigned int i = 0; i < patternString.size(); i++)
{
patternStringHash[patternString.at(i)]++;
}
unsigned int count = 0;
unsigned int start = 0;
unsigned int start_index = INT_MAX;
unsigned int min_len = INT_MAX;
for (unsigned int i = 0; i < sourceString.size(); i++)
{
if (patternStringHash[sourceString.at(i)] == 0)
{
continue;
}
sourceStringHash[sourceString.at(i)]++;
if (sourceStringHash[sourceString.at(i)] <= patternStringHash[sourceString.at(i)])
{
count++;
}
if (count == patternString.size())
{
while(sourceStringHash[sourceString.at(start)] > patternStringHash[sourceString.at(start)] || patternStringHash[sourceString.at(start)] == 0)
{
if(sourceStringHash[sourceString.at(start)] > patternStringHash[sourceString.at(start)])
{
sourceStringHash[sourceString.at(start)] --;
}
start++;
}
unsigned int len_window = i - start + 1;
if (min_len > len_window)
{
min_len = len_window;
start_index = start;
}
}
}
if (start_index == INT_MAX)
{
cout << “No such window exists”;
return “”;
}
return sourceString.substr(start_index, min_len);
}
int
main()
{
string sourceString, patternString;
getline(cin, sourceString);
getline(cin, patternString);
cout << findSubString(sourceString, patternString) << endl;
return 0;
}