title: find the minimum window in string S which will contain all the characters of string T
body: <blockquote>
    <p>Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).</p>
  </blockquote>
  
  <p>For example,</p>
  
  <pre><code>S = "ADOBECODEBANC"
  T = "ABC"
  </code></pre>
  
  <p>Minimum window is <code>"BANC"</code>.</p>
  
  <pre><code>void getstring(char str1[],char str2[],char hash[])
  {
  
      int len=strlen(str1);
      int i=0,j;              //i keeps the previous index
      int min=INT_MAX;
      int cnt=0;  
      for(j=0;j&lt;len;j++)
          {
              if(hash[str1[j]]==-1)   //means uninitialized, will be checked for first time only
              {
  
                  cnt++;              
                  hash[str1[j]]=j;                    
  
                  if(cnt==1)
                  i=j;
  
                  int y=check(hash,str2); //checking for the characters
                  //printf("y=%d",y);
                  if(y)       //means all the characters are present
                  {
                      if( (j-i+1)&lt;min)
                      {
                      min=j-i+1;
                      I=i;
                      J=j;
                      }               
  
  
                  }
  
  
                 }
                  else if(hash[str1[j]]&gt;=0)
                  {
  
  
                      hash[str1[j]]=j;
  
  
  
                      if(check(hash,str2) )
                      {                   
  
                      if( hash[str1[i]]==hash[str1[j]] )      //it means that we are moving the first
                      {                       //index only
                      i=getmin(hash,str2);    //get minimum index of the element              
  
                          if( (j-i+1)&lt;min)
                          {
                              min=j-i+1;
                              I=i;
                              J=j;
                          }
  
  
                      }
                      //else
                      }
                      else
                      {
                      if( hash[str1[i]]==hash[str1[j]] )
                      i=hash[str1[i]];                        
                      }
  
                  }//end of else-if
                  }//end of for    
  }
  </code></pre>
  
  <p>I have made the code for it using hash i.e. i am keeping the index values of the characters of the string T in the hash and using two indexes, as soon as i get any character ahead same as the character at the lower index, i first check the length and then updates the index.</p>
  
  <p>This approach would take O(nk) in worst case.</p>
  
  <pre><code>n - is the number of characters in S
  k - is the number of characters in T
  </code></pre>
  
  <p>Is there any approach which will take <code>O(n)</code> time for this problem?</p>