1) Make an integer array shouldfind[] of len 256 . i-th element of this array will have a the count how many times we need to find element of ASCII value i.
2) Make another array hasfound of 256 elements, which will have the count of required element found till now.
3) Count <= 0
4) While input[i]
. a. If input[i] element is not to be found -> continue
. b. If input[i] element is required => increase count by 1.
. c. If count is length of chars[] array, slide the window as much right as possible.
. d. If current window length is less than min length found till now. Update min length.
5) end
Code:
#define MAX 256
void minlengthwindow(char input[], char chars[], int &start, int &finish)
{
int shouldfind[MAX] = {0,};
int hasfound[MAX] = {0,};
int cnt = 0;
int minwindow = INT_MAX;
int charlen = strlen(chars);
for (int i=0; i< charlen; i++)
shouldfind[chars[i]] += 1;
int iplen = strlen(input);
start = 0;
finish = iplen;
int j = 0;
for (int i=0; i< iplen; i++)
{
if (!shouldfind[input[i]])
continue;
hasfound[input[i]] += 1;
if (shouldfind[input[i]] >= hasfound[input[i]])
cnt++;
if (cnt == charlen)
{
while (shouldfind[input[j]] == 0 || hasfound[input[j]] > shouldfind[input[j]])
{
if (hasfound[input[j]] > shouldfind[input[j]])
hasfound[input[j]]--;
j++;
}
if (minwindow > (i - j +1))
{
minwindow = i - j +1;
finish = i;
start = j;
}
}
}
cout << start << " " << finish << endl;
}
Complexity: If you walk through the code, i and j can traverse at most N steps (where N is input size size) in the worst case, adding to a total of 2N times. Therefore, time complexity is O(N).
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.