Easier to read as using a customized map class


  • 0
    U

    class Solution {

    public static class CountMap {
        private Map<Character, Integer> standardMap; // should be immutable
        private Map<Character, Integer> countMap;
        private int diff;
        
        public CountMap(String t) {
            standardMap = new HashMap();
            countMap = new HashMap();
            for (Character c: t.toCharArray()) {
                if (!standardMap.containsKey(c)) {
                    standardMap.put(c, 0);
                    countMap.put(c, 0);
                }
                standardMap.put(c, standardMap.get(c) + 1);
            }
            diff = t.length();
        }
        
        public void addChar(char c) {
            if (countMap.containsKey(c)) {
                if (countMap.get(c) < standardMap.get(c)) {
                    diff--;
                }
                countMap.put(c, countMap.get(c) + 1);
            }
        }
        
        public void removeChar(char c) {
            if (countMap.containsKey(c)) {
                if (countMap.get(c) <= standardMap.get(c)) {
                    diff++;
                }
                countMap.put(c, countMap.get(c) - 1);
            }
        }
        
        public int getDiff() {
            return diff;
        }
    }
    public String minWindow(String s, String t) {
        CountMap map = new CountMap(t);
        int i = 0;
        int j = 0;
        int minLen = s.length();
        String minWindow = "";
        while(j < s.length()) {
            map.addChar(s.charAt(j));
            if (map.getDiff() == 0) {
                while(map.getDiff() == 0) {
                    map.removeChar(s.charAt(i));
                    i++;                    
                }                
                // (i-1) to j should contains all character in t
                if (j - i + 2 <= minLen) {
                    minLen = j-i+2;
                    minWindow = s.substring(i-1, j+1);
                }
            }
            j++;
        }
    
        return minWindow;
    }
    

    }


Log in to reply
 

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