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".

Answer:
This algorithm is based on sliding window approach. In this approach, you start from the beginning of the array and move to right. As soon as you have a window, which have all the required elements, try sliding the window to as much right as possible with all the required elements. If current window length is less than min length found till now, update min length.

For Example of your input array is “ABBACBAA” and minimum window should cover characters “AAB” then sliding window will move like this:

Algorithm
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

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.