find the minimum window in string S which will contain all the characters of string T

Question

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

For example,

S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

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<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)<min)
                    {
                    min=j-i+1;
                    I=i;
                    J=j;
                    }               


                }


               }
                else if(hash[str1[j]]>=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)<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    
}

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.

This approach would take O(nk) in worst case.

n - is the number of characters in S
k - is the number of characters in T

Is there any approach which will take O(n) time for this problem?

Could you include all of your code, including `getmin()` and `check()` and format your code properly? — svick, Jun 02 '12 at 21:46
Actually its not giving right output for all test cases, so i have not included the whole code. — Luv, Jun 02 '12 at 21:50
possible duplicate of [An efficient algorithm for finding smallest pangrammatic windows?](http://stackoverflow.com/questions/9775301/an-efficient-algorithm-for-finding-smallest-pangrammatic-windows) — templatetypedef, Jun 02 '12 at 22:01
same as http://stackoverflow.com/questions/925922/algorithm-to-determine-indices-i-j-of-array-a-containing-all-the-elements-of-an — Ravi Gupta, Jun 03 '12 at 07:05
Possible duplicate of [Minimum window width in string x that contains all characters in string y](https://stackoverflow.com/questions/3592079/minimum-window-width-in-string-x-that-contains-all-characters-in-string-y) — roottraveller, Aug 31 '17 at 12:16

score 3 · Accepted Answer · answered Jun 02 '12 at 22:12

3

So make a pass of S keeping track of when you last saw each letter in T.

At each point the farthest of the last seen letters will delimit the left edge of a window (with the current point being the right edge).

Of these windows, simply keep track of the smallest one seen so far. At the end of the algorithm this will be the smallest window overall.

answered Jun 02 '12 at 22:12

Andrew Tomazos

66,139
40
186
319

I have done exactly same but one thing is missing, I will correct it. – Luv Jun 02 '12 at 22:28
2

I think more details on how to update and keep track of these windows would be helpful. – IVlad Jun 02 '12 at 22:29
1

Keeping track of the minimum window seen is just `if (current < min) min = current` at each step. The set of last seen characters needs to be indexed by a perfect hash by character (an array), and also by a linked list by order of last seen. When the last seen changes it needs to be removed from list and placed at head. The tail of the list then will give the farthest last seen, and left edge of window. `current_window_size = current_pos - last_seen_pos`. These are all O(1) operations. – Andrew Tomazos Jun 03 '12 at 06:57
But how will you handle the case if S="AAAAAAA" and T="AA".In this case we will keep on removing and inserting 'A'. And the linked list will be of 1 character. Hence we will not get "AA". – Luv Jun 03 '12 at 08:21
You're description didn't specify what happens in the case of duplicate characters. In the case described you have to keep track of the kth last seen character c, where k is the number of occurences of the character c in T. This just requires keeping count of the (now multiple) number of entries of c in the last seen list, and making sure not to remove any until k have been added for the first time. – Andrew Tomazos Jun 03 '12 at 08:34

score 0 · Answer 2 · answered Sep 06 '15 at 08:10

Here is my java code which has passed all the test cases. I hope it might help you as well.

public class Solution {
    public String minWindow(String s, String t) {

         if(t.length()>s.length()) 
        return "";
    String result = "";

     HashMap <Character, Integer> shouldFind = new HashMap<Character, Integer>();
     HashMap <Character, Integer> hasFound = new HashMap<Character, Integer>();
     int count =0, j=0,  minWindow = s.length()+1, start=0, finish =0;

     Integer sLength = s.length();
     Integer tLength = t.length();

     for(int i = 0 ; i < tLength ; i++)
     {
         char tChar = t.charAt(i);
         if(!shouldFind.containsKey(tChar))
         shouldFind.put(tChar,1);
         else 
         shouldFind.put (tChar ,shouldFind.get(tChar)+1);

     }


     for (int i =0; i <sLength; i ++)
     {
         char sChar = s.charAt(i);

         if(shouldFind.containsKey(sChar))
         {
             if(!hasFound.containsKey(sChar)){
             hasFound.put(sChar, 1);
             count++;
             }
             else {
                 if(hasFound.get(sChar) < shouldFind.get(sChar) )
                 count ++;

             hasFound.put(sChar, hasFound.get(sChar) +1);

             }
         }




        if(count == tLength)
        {
            char ch = s.charAt(j);

          while (!hasFound.containsKey(ch) || hasFound.get(ch) > shouldFind.get(ch))
          {
              if(hasFound.containsKey(ch) && hasFound.get(ch)>shouldFind.get(ch))
              hasFound.put(ch , hasFound.get(ch) -1);

              j++;
              ch = s.charAt(j);
          }

            //lets find the minimum window
            if(minWindow > (i-j+1) )
            {
                minWindow = i - j + 1;
                start = j;
                finish = i+1;
                result = s.substring(start, finish);

            }

        }}




        return result;
    }}

find the minimum window in string S which will contain all the characters of string T

2 Answers2