Java code with comment. O(n)


  • 1
    Z
    /**
     * Use hashmap/array to determine coverage.
     * 
     * Two pointer: 
     *  left and right starts from 0, right move minimally to make a cover, left move aggressively while mantaining the cover.
     *  keep updating ansser. 
     */ 
    public class Solution {
        public String minWindow(String s, String t) {
            int[] tmap = freq(t);
            int[] wmap = freq("");
            
            String ret = "";
            int min = Integer.MAX_VALUE;
            // right is inclusive
            for(int left =0, right = 0; right < s.length(); right ++){
                wmap[s.charAt(right)] ++;
                if(!isCover(wmap, tmap))
                    continue;
                
                // move left pointer aggressively, mantaining coverage   
                while(left <= right){
                    char c = s.charAt(left);
                    if(wmap[c]  == tmap[c])
                        break;
                        
                    wmap[c] --;
                    left ++;
                }
                
                String w = s.substring(left, right +1);
                if(w.length() < min){
                    min = w.length();
                    ret = w;
                }
            }
            
            return ret;
        }
        
        // true iff a is cover of b
        boolean isCover(int[] a, int[] b){
            for(int i=0; i <a.length; i ++){
                if(a[i] < b[i])
                    return false;
            }
            return true;
        }
        
        // get char freq array from string
        int[] freq(String s){
            int[] ret = new int[256];
            for(char c : s.toCharArray()){
                ret[c] ++;
            }
            
            return ret;
        }
    }
    
    

  • 0

    very good solution, very readable.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.