28 Jun 2014

Minimum Window Containing all words

Problem Statement:
   Find the minimum window in which all the words of the pattern string are present in the input string.

Text  "Shopping with xyz.com is an awesome experience"
Pattern : "awesome with xyz.com"

Output : "with  xyz.com  is  an  awesome"

The output window contains all words of pattern in text.

Download Source Code
Solution:

The approach to solve the problem is to have two pointers of the window , as left and right.
The right pointer is moved to the right until all words in the text are found, once all the required words are found the left pointer is moved to its right to discard  the words on the left hand of the window.

The approach used is based on Sliding Window. In this approach we take pointers at extreme left and extreme right. The right pointer is moved to its right in search of required words, once the window contains all required words, the left pointer tries to decrease size of the window with all the required words.
If the current window length is smaller smaller than previous one , it is recorded or updated.

Complexity: O(n) + O(n)  = O(n)

Below is the implementation

private static int minWindow = 9999; // length of minimum window
 private static int startWord = 0; // start position
 private static int endWord = 0; // end position
 /**
  * Sub-routine to minumum window in which all words of pattern are found in
  * the given string
  * @param str : input String
  * @param pat : pattern
  */
 public static void minWindow(String str, String pat)
 {

  // words to be found
  Map toFind = new HashMap(); 
  // the set of  words  which are found
  Map found = new HashMap(); 

  int foundCount = 0;
  // left pointer of the window, which is moved when all required wrds are
  // found,
  // and is moved until any word from required word is found
  int tempStart = 0;

  // Tokenising Text
  String[] words = str.split(" ");
  int sLen = words.length;

  // Tokenising Pattern
  String[] patTokens = pat.split(" ");
  int pLen = patTokens.length;

  // filling the 'toFind' map
  for (String val : patTokens)
   toFind.put(val, toFind.get(val) == null ? 1 : toFind.get(val) + 1);

  // traversing over text length
  for (int index = 0; index < sLen; index++)
  {
   String word = words[index];

   if (!toFind.containsKey(word))
    continue;

   found.put(word, found.get(word) == null ? 1 : found.get(word) + 1);

   if (toFind.get(word) >= found.get(word))
    foundCount++;

   if (foundCount == pLen) 
   {
    // reduce window size until conditions are violated
    word = words[tempStart];
    while (!toFind.containsKey(word)
      || toFind.get(word) < found.get(word)) 
    {
     // Discard excess count of the given word
     if (toFind.containsKey(word))
      found.put(word, found.get(word) - 1);

     // get next word, to check if it can be discarded
     word = words[++tempStart];
    }

    // Updating Min Window
    if (minWindow > index - tempStart + 1)
    {
     minWindow = index - tempStart + 1;
     startWord = tempStart;
     endWord = index;
    }
   }
  }
 }


Please comment and post your suggestions.
Happy Coding !! :)

No comments:

Post a Comment