WAP to Finding The Minimum Window In An Array Which Contains All Given Elements (Need Not to be Contiguous)

Question: Given a set CHARS of characters and a string INPUT, find the minimum window in INPUT which will contain all the characters in CHARS in complexity O(n).

Ex:
INPUT = "ABBACBAA"
CHARS = "AAB"

Minimum window is "BAA".

For example
Test length
[A B B A] C B A A 4
A B B [A C B A] A 4
[A B B A] C [B A A] 3 answer


lgorithm
Input is the given array and chars is the array of character need to be found.

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



#include
#include
#include
#include
using namespace std;

#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;
}


int main()
{
char a[]="ABBACBAA";
int size=sizeof(a)/sizeof(int);
char chars[]="AAB";
minlengthwindow(a,chars,0,size);


}


TC O(N) 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).

SC O(1)
Run Here http://ideone.com/kJwMS