Java solution. using two pointers + HashMap


  • 31
    public class Solution {
    public String minWindow(String s, String t) {
        if(s == null || s.length() < t.length() || s.length() == 0){
            return "";
        }
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for(char c : t.toCharArray()){
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
        int left = 0;
        int minLeft = 0;
        int minLen = s.length()+1;
        int count = 0;
        for(int right = 0; right < s.length(); right++){
            if(map.containsKey(s.charAt(right))){
                map.put(s.charAt(right),map.get(s.charAt(right))-1);
                if(map.get(s.charAt(right)) >= 0){
                    count ++;
                }
                while(count == t.length()){
                    if(right-left+1 < minLen){
                        minLeft = left;
                        minLen = right-left+1;
                    }
                    if(map.containsKey(s.charAt(left))){
                        map.put(s.charAt(left),map.get(s.charAt(left))+1);
                        if(map.get(s.charAt(left)) > 0){
                            count --;
                        }
                    }
                    left ++ ;
                }
            }
        }
        if(minLen>s.length())  
        {  
            return "";  
        }  
        
        return s.substring(minLeft,minLeft+minLen);
    }
    

    }


  • 0

    Really brilliant solution using just one hashmap.


  • 0
    R

    can you give us some explaination? i can't understand your idea.


  • 0
    D

    Beautiful solution!


  • 13
    L

    @ruo here is my comment.
    Generally, there are following steps:

    1. create a hashmap for each character in t and count their frequency in t as the value of hashmap.
    2. Find the first window in S that contains T. But how? there the author uses the count.
    3. Checking from the leftmost index of the window and to see if it belongs to t. The reason we do so is that we want to shrink the size of the window.
      3-1) If the character at leftmost index does not belong to t, we can directly remove this leftmost value and update our window(its minLeft and minLen value)
      3-2) If the character indeed exists in t, we still remove it, but in the next step, we will increase the right pointer and expect the removed character. If find so, repeat step 3.
    public String minWindow(String s, String t) {
            HashMap<Character, Integer> map = new HashMap();
            for(char c : t.toCharArray()){
                if(map.containsKey(c)){
                    map.put(c, map.get(c)+1);
                }
                else{
                    map.put(c, 1);
                }
            }
            int left = 0, minLeft=0, minLen =s.length()+1, count = 0;
            for(int right = 0; right<s.length(); right++){
                char r = s.charAt(right);
                if(map.containsKey(r)){//the goal of this part is to get the first window that contains whole t
                    map.put(r, map.get(r)-1);
                    if(map.get(r)>=0) count++;//identify if the first window is found by counting frequency of the characters of t showing up in S
                }
                while(count == t.length()){//if the count is equal to the length of t, then we find such window
                    if(right-left+1 < minLen){//jsut update the minleft and minlen value
                        minLeft = left;
                        minLen = right-left+1;
                    }
                    char l = s.charAt(left);
                    if(map.containsKey(l)){//starting from the leftmost index of the window, we want to check if s[left] is in t. If so, we will remove it from the window, and increase 1 time on its counter in hashmap which means we will expect the same character later by shifting right index. At the same time, we need to reduce the size of the window due to the removal.
                        map.put(l, map.get(l)+1);
                        if(map.get(l)>0) count--;
                    }
                    left++;//if it doesn't exist in t, it is not supposed to be in the window, left++. If it does exist in t, the reason is stated as above. left++.
                }
            }
            return minLen==s.length()+1?"":s.substring(minLeft, minLeft+minLen);
        }
    

  • 0
    D
    This post is deleted!

  • 0
    E

    @liang54 very helpful. Thanks!


  • 0
    C

    I get the feeling that this line is redundant. Anyone agree?

    map.put(r, map.get(r)-1);
    

  • 0
    L

    @chsekhar No, it's used to update the number of char r to be found in the map, so that the left edge of window could move to right with subtacting the count or not.

    For example, for the s-string "aabcd" and the t-string "abc". The map is [[a,1], [b,1], [c,1]] at first;
    After visiting the first 'a', it becomes [[a,0], [b,1], [c,1]];
    Then the second 'a', [[a,-1], [b,1], [c,1]];
    When you reach the 'c', you get a map [[a,-1], [b,0], [c,0]] with count == 3. Then you update minLeft & minLen. Now it's important:

    You should add 1 to the value in the map according to the left char('a'), so the map is now [[a,0], [b,0], [c,0]];
    Since the value according to the left char 'a' is still not greater than 0(no need to find another 'a'), so you move the left edge of the window moves 1 unit right without subtracting count;
    The count is still 3 so you go through the loop again, this time the map will be [[a,1], [b,0], [c,0]], so the left edge of the window 1 unit with subtracting count.


  • 0
    P

    @LetianFeng Awesome solution. What is the complexity of this solution


Log in to reply
 

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