Share my code (HashMap + Two Pointers)


  • 0
    T

    Increase fast pointer until covering all the characters
    then increase slow pointer to squeeze the range only if

    1. s.charAt(slow) not in the map or 2. map.get(s.charAt(slow)) < 0
        public String minWindow(String s, String t) {
            int[] index = {0, -1};
            int match,fast,slow;
            fast = match = slow = 0;
            int min = Integer.MAX_VALUE;
            Map<Character, Integer> map = getMap(t);
            
            while(fast < s.length()){
                Integer count = map.get(s.charAt(fast));
                if(count != null){
                    if(count == 1) match++;
                    map.put(s.charAt(fast), count - 1);
                }
    
                if(match == map.size()){
                    while(!map.containsKey(s.charAt(slow)) || map.get(s.charAt(slow)) < 0){
                        Integer num = map.get(s.charAt(slow));
                        if(num != null){
                            map.put(s.charAt(slow), num + 1);
                        }
                        slow++;
                    }
                    if(fast - slow + 1 < min){
                        min = fast - slow + 1;
                        index[0] = slow;
                        index[1] = fast;
                    }
                }
                fast++;
            }
            return s.substring(index[0], index[1] + 1);
        }
    
        public Map<Character, Integer> getMap(String t){
            Map<Character, Integer> map = new HashMap<>();
            for(int i = 0; i < t.length(); i++){
                Integer num = map.get(t.charAt(i));
                if(num == null){
                    map.put(t.charAt(i), 1);
                }else{
                    map.put(t.charAt(i), num + 1);
                }
            }
            return map;
        }
    

Log in to reply
 

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