Labels

Sunday, March 29, 2015

Minimum Window Substring

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".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Naive Way: In order to find a minimum window, there must be a way to represent the pattern (which is T) here and current accumulate characters set. A map is suitable to deal with that. Map each character to # of its appearance. And then, need to find a way to keep track of every possible position when a match was found and you need to delete the first character from current accumulate char set. A queue is suitable to do that.

A case when S = "bba" and T="ab" leads to  this line.
  while(isMatch(pattern, cur)){ /* Important Code! */  

One shortcoming is isMatch() funciton takes O(T) time.

 public class Solution {  
   public String minWindow(String S, String T) {  
     Map<Character, Integer> pattern = new HashMap<Character, Integer>();  
     Map<Character, Integer> cur = new HashMap<Character, Integer>();  
     Queue<Integer> queue = new LinkedList<Integer>();  
     int min = Integer.MAX_VALUE;  
     int begin = 0, end = 0;  
     // fill in pattern by T  
     for(int i = 0;i < T.length();i++) addToMap(pattern, T.charAt(i));  
     // initialize current set  
     for(int i = 0;i < T.length();i++) cur.put(T.charAt(i), 0);  
     // go through S to match the pattern by minimum length  
     for(int i = 0;i < S.length();i++){  
       if(pattern.containsKey(S.charAt(i))){  
         queue.add(i);  
         addToMap(cur, S.charAt(i));  
         // check if pattern is matched  
         while(isMatch(pattern, cur)){ /* Important Code! */  
           if(i - queue.peek() < min){  
             min = i - queue.peek();  
             begin = queue.peek();  
             end = i+1;  
           }  
           cur.put(S.charAt(queue.peek()), cur.get(S.charAt(queue.peek()))-1);  
           queue.poll();  
         }  
       }  
     }  
     return end > begin?S.substring(begin, end):"";  
   }  
   private void addToMap(Map<Character, Integer> map, Character c){  
     if(map.containsKey(c))  
       map.put(c, map.get(c)+1);  
     else  
       map.put(c,1);  
   }  
   private boolean isMatch(Map<Character, Integer> p, Map<Character, Integer> cur){  
     for(Map.Entry<Character, Integer> entry: p.entrySet())  
       if(cur.get((char)entry.getKey()) < (int)entry.getValue()) return false;  
     return true;  
   }  
 }  

No comments:

Post a Comment