Java accepted Solution with HashMap and two pointers


  • 0
    public class Solution {
    public String minWindow(String s, String t) {   
        Map<Character,Integer> map = new HashMap<Character,Integer>();    
        for (char ch : t.toCharArray()){
            if(!map.containsKey(ch))map.put(ch,1);
            else map.put(ch,map.get(ch)+1);
        }
        int len = t.length();
        String res = "";
        int left = 0, min = Integer.MAX_VALUE;         
        for (int i = 0; i < s.length(); i++){// sliding window: left, right(i);
            char tem = s.charAt(i);
            if(map.containsKey(tem)){
                map.put(tem,map.get(tem)-1);
                if(map.get(tem)>=0)len--;
            }
            while(len==0 && left<=i){
                tem = s.charAt(left);
                if(map.containsKey(tem) && map.get(tem)==0){
                    break;
                }else if(map.containsKey(tem) && map.get(tem)<0){
                    left++;
                    map.put(tem,map.get(tem)+1);
                }else{left++;}
            }
            if(len==0 && min>i-left+1){
                min=i-left+1;
                res=s.substring(left,i+1);
            }
        }
        return res;
    }
    

    }


Log in to reply
 

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