Find the smallest window in a string containing all characters of another string

Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.

For Example:

Input string1: “this is a test string”
Input string2: “tist”

Output string: “t stri”

Method 1 ( Brute force solution )
a) Generate all substrings of string1 (“this is a test string”)
b) For each substring, check whether the substring contains all characters of string2 (“tist”)
c) Finally print the smallest substring containing all characters of string2.

Method 2 ( Optimized Brute Force ) 
a)  calculate positions of characters of String2("tist") from String1 ("this is a test string")
that is
postition['t'] = {0,10,13, 16}
postition['i'] = {2,5,18}
postition['s'] = {3,6,12,15}

b) permutations = positions['t'] * positions['i'] * positions['s'] * positions['t']
ie : permutation = { { 0, 2,3,10} , {0,5,6,10} ...... }
Find the one which has smallest gap in all ...
ie : {13,18,15,16}
(This we can find from min in set and max in set.)

Method 3) Create Table for index and find 

- Take help of two pointers "begin" and "end" position of the window. Two tables "needToFind" and "hasFound" while traversing String1.
- "needToFind" stores the total count of a character in String2("tist") and "hasFound" stores the total count of a character met so far from String1("this is ...")
- keep "count" variable to store the total characters in String2 that’s met so far (not counting characters where hasFound[x] exceeds needToFind[x])

Procedure

- We Start checking String1 from begin & end as 0,0 window to 0,strlen(String1) length.
- When ever we find a character need to be in String2.
 We check count of occurance
if its >= needing count (needToFind) then we increment count.

When found are matching needTofind window fully
ie . all character of String2 are in 0 to t index of Sting1
like in out example "this is a t"
we store total count.
- now we increase begin and see if new window contains all character count needing.
and we proceed

else we increment end ( maximizing the window..)

Check Workig Code at http://ideone.com/79jBH9




Function :

bool minWindow(const char* S, const char *T, int &minWindowBegin, int &minWindowEnd) {
  int sLen = strlen(S);
  int tLen = strlen(T);
  int needToFind[256] = {0};



  for (int i = 0; i < tLen; i++)
    needToFind[T[i]]++;

  int hasFound[256] = {0};
  int minWindowLen = INT_MAX;
  int count = 0;
  int begin,end,windowLen;
  for (begin = 0, end = 0; end < sLen; end++) {

    if (needToFind[S[end]] == 0) continue;
    hasFound[S[end]]++;
    if (hasFound[S[end]] <= needToFind[S[end]])
      count++;


    if (count == tLen) {

      while (needToFind[S[begin]] == 0 || hasFound[S[begin]] > needToFind[S[begin]]) {
        if (hasFound[S[begin]] > needToFind[S[begin]])
          hasFound[S[begin]]--;
        begin++;
      }

      windowLen = end - begin + 1;
      //cout<<windowLen<<endl;
      if (windowLen < minWindowLen) {
        minWindowBegin = begin;
        minWindowEnd = end;
        minWindowLen = windowLen;
      } // end if
    } // end if
  } // end for
  
  //seeting end limit if we found such window
 if(count == tLen){
  while(1){
  if (needToFind[S[end]] == 0) end--;
  else break;
  }//while
  cout<<begin<<"-"<<end<<endl;
  return true;
}//if
return false;  
}
int main() {
// your code goes here
int begin=0, end=0;
cout<<minWindow("this is a test string","tist",begin, end);
return 0;
}

If you want to share such question , solution  or your experience of any company, Please do share at admin@gohired.in , As sharing is caring