Java simple solution with TreeSet


  • 0
    V
    public String minWindow(String s, String t) {
            HashMap<Character, Integer> map = new HashMap<>();
            HashMap<Character, TreeSet<Integer>> charmap = new HashMap<>();
            TreeSet<Integer> set = new TreeSet<>();
            String answer = "";
            int shortest = Integer.MAX_VALUE;
            for(int i = 0; i < t.length(); i++){
                char c = t.charAt(i);
                if(map.containsKey(c)) map.put(c, map.get(c)+1);
                else map.put(c, 1);
            }
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                if(map.containsKey(c)){
                    if(charmap.containsKey(c)){
                        if(map.get(c) == charmap.get(c).size()){
                            set.remove(charmap.get(c).pollFirst());
                        }
                        charmap.get(c).add(i);
                    } else{
                        TreeSet<Integer> ts = new TreeSet<>();
                        ts.add(i);
                        charmap.put(c, ts);
                    }
                    set.add(i);
                    if(set.size() == t.length()){
                        int lowest = set.first();
                        if(i - lowest < shortest){
                            answer = s.substring(lowest, i+1);
                            shortest = i - lowest;
                        }
                    }
                }
            }
            return answer;
        }

Log in to reply
 

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